Search Results

Search found 89 results on 4 pages for 'polynomial'.

Page 4/4 | < Previous Page | 1 2 3 4 

• Genetic Algorithms applied to Curve Fitting

  - by devoured elysium

  Let's imagine I have an unknown function that I want to approximate via Genetic Algorithms. For this case, I'll assume it is y = 2x. I'd have a DNA composed of 5 elements, one y for each x, from x = 0 to x = 4, in which, after a lot of trials and computation and I'd arrive near something of the form: best_adn = [ 0, 2, 4, 6, 8 ] Keep in mind I don't know beforehand if it is a linear function, a polynomial or something way more ugly, Also, my goal is not to infer from the best_adn what is the type of function, I just want those points, so I can use them later. This was just an example problem. In my case, instead of having only 5 points in the DNA, I have something like 50 or 100. What is the best approach with GA to find the best set of points? Generating a population of 100, discard the worse 20% Recombine the remaining 80%? How? Cutting them at a random point and then putting together the first part of ADN of the father with the second part of ADN of the mother? Mutation, how should I define in this kind of problem mutation? Is it worth using Elitism? Any other simple idea worth using around? Thanks

  Read the article

• Calculating Nearest Match to Mean/Stddev Pair With LibSVM

  - by Chris S

  I'm new to SVMs, and I'm trying to use the Python interface to libsvm to classify a sample containing a mean and stddev. However, I'm getting nonsensical results. Is this task inappropriate for SVMs or is there an error in my use of libsvm? Below is the simple Python script I'm using to test: #!/usr/bin/env python # Simple classifier test. # Adapted from the svm_test.py file included in the standard libsvm distribution. from collections import defaultdict from svm import * # Define our sparse data formatted training and testing sets. labels = [1,2,3,4] train = [ # key: 0=mean, 1=stddev {0:2.5,1:3.5}, {0:5,1:1.2}, {0:7,1:3.3}, {0:10.3,1:0.3}, ] problem = svm_problem(labels, train) test = [ ({0:3, 1:3.11},1), ({0:7.3,1:3.1},3), ({0:7,1:3.3},3), ({0:9.8,1:0.5},4), ] # Test classifiers. kernels = [LINEAR, POLY, RBF] kname = ['linear','polynomial','rbf'] correct = defaultdict(int) for kn,kt in zip(kname,kernels): print kt param = svm_parameter(kernel_type = kt, C=10, probability = 1) model = svm_model(problem, param) for test_sample,correct_label in test: pred_label, pred_probability = model.predict_probability(test_sample) correct[kn] += pred_label == correct_label # Show results. print '-'*80 print 'Accuracy:' for kn,correct_count in correct.iteritems(): print '\t',kn, '%.6f (%i of %i)' % (correct_count/float(len(test)), correct_count, len(test)) The domain seems fairly simple. I'd expect that if it's trained to know a mean of 2.5 means label 1, then when it sees a mean of 2.4, it should return label 1 as the most likely classification. However, each kernel has an accuracy of 0%. Why is this? On a side note, is there a way to hide all the verbose training output dumped by libsvm in the terminal? I've searched libsvm's docs and code, but I can't find any way to turn this off.

  Read the article

• C malloc assertion help

  - by Chris

  I am implementing a divide and conquer polynomial algorithm so i can bench it against an opencl implementation, but i can't seem to get malloc to work. When I run the program it allocates a bunch of stuff, checks some things, then sends the size/2 to the algorithm. Then when I hit the malloc line again it spits out this: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)-bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) = (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)-size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed. Aborted The line in question is: int *out, .....other vars....; out = (int *)malloc(sizeof(int) * size * 2); I have checked size with fprintf and it is a positive int (usually 50 at that point). I have tried calling malloc with a plain number as well and i still get the error. I'm just stumped at what's going on, and nothing from google that I have found so far has been too helpful. Any ideas what's going on? I'm trying to figure out how to compile a newer GCC in case it's a compiler error, but i really doubt it.

  Read the article

• Find the Algorithm that generates the checksum

  - by knivmannen

  I have a sensing device that transmits a 6-byte message along with an 1-byte counter and supposely a checksum. The data looks something like this: ------DATA----------- -Counter- --Checksum?-- 55 FF 00 00 EC FF ---- 60---------- 1F The last four bits in the counter are always set 0, i.e those bits are probably not used. The last byte is assumed to be the checksum since it has a quite peculiar nature. It tends to randomly change as data changes. Now what i need is to find the algorithm to compute this checksum based on --DATA--. what i have tried is all possible CRC-8 polynomials, for each polynomial i have tried to reflect data, toggle it, initiate it with non-zeroes etc etc. Ive come to the conclusion that i am not dealing with a normal crc-algorithm. I have also tried some flether and adler methods without succes, xor stuff back and forth but still i have no clue how to generate the checksum. My biggest concern is, how is the counter used??? Same data but with different countervalue generates different checksums. I have tried to include the counter in my computations but without any luck. Here are some other datasamples: 55 FF 00 00 F0 FF A0 38 66 0B EA FF BF FF C0 CA 5E 18 EA FF B7 FF 60 BD F6 30 16 00 FC FE 10 81 One more thing that might be worth mentioning is that the last byte in the data only takes on the values FF or FE Plz if u have any tips or tricks that i may try post them here, I am truly desperate. Thx

  Read the article

• How to calculate this string-dissimilarity function efficiently?

  - by ybungalobill

  Hello, I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close to "worldhello". Obviously Levenshtein distance and Longest common subsequence don't fulfill this requirement. Using Jaccard distance on the set of n-grams gives good results but has other drawbacks (it's a pseudometric and higher n results in higher penalty for changing single character). [original research] As I thought about it, what I'm looking for is a function f(A,B) such that f(A,B)+1 equals the minimum number of blocks that one have to divide A into (A1 ... An), apply a permutation on the blocks and get B: f("hello", "hello") = 0 f("helloworld", "worldhello") = 1 // hello world -> world hello f("abba", "baba") = 2 // ab b a -> b ab a f("computer", "copmuter") = 3 // co m p uter -> co p m uter This can be extended for A and B that aren't necessarily permutations of each other: any additional character that can't be matched is considered as one additional block. f("computer", "combuter") = 3 // com uter -> com uter, unmatched: p and b. Observing that instead of counting blocks we can count the number of pairs of indices that are taken apart by a permutation, we can write f(A,B) formally as: f(A,B) = min { C(P) | P:|A|?|B|, P is bijective, ?i?dom(P) A[P(i)]=B[P(i)] } C(P) = |A| + |B| - |dom(P)| - |{ i | i,i+1?dom(P) and P(i)+1=P(i+1) }| - 1 The problem is... guess what... ... that I'm not able to calculate this in polynomial time. Can someone suggest a way to do this efficiently? Or perhaps point me to already known metric that exhibits similar properties?

  Read the article

• Ad distribution problem: an optimal solution?

  - by Mokuchan

  I'm asked to find a 2 approximate solution to this problem: You’re consulting for an e-commerce site that receives a large number of visitors each day. For each visitor i, where i € {1, 2 ..... n}, the site has assigned a value v[i], representing the expected revenue that can be obtained from this customer. Each visitor i is shown one of m possible ads A1, A2 ..... An as they enter the site. The site wants a selection of one ad for each customer so that each ad is seen, overall, by a set of customers of reasonably large total weight. Thus, given a selection of one ad for each customer, we will define the spread of this selection to be the minimum, over j = 1, 2 ..... m, of the total weight of all customers who were shown ad Aj. Example Suppose there are six customers with values 3, 4, 12, 2, 4, 6, and there are m = 3 ads. Then, in this instance, one could achieve a spread of 9 by showing ad A1 to customers 1, 2, 4, ad A2 to customer 3, and ad A3 to customers 5 and 6. The ultimate goal is to find a selection of an ad for each customer that maximizes the spread. Unfortunately, this optimization problem is NP-hard (you don’t have to prove this). So instead give a polynomial-time algorithm that approximates the maximum spread within a factor of 2. The solution I found is the following: Order visitors values in descending order Add the next visitor value (i.e. assign the visitor) to the Ad with the current lowest total value Repeat This solution actually seems to always find the optimal solution, or I simply can't find a counterexample. Can you find it? Is this a non-polinomial solution and I just can't see it?

  Read the article

• python crc32 woes

  - by lazyr

  I'm writing a python program to extract data from the middle of a 6 GB bz2 file. A bzip2 file is made up of independently decryptable blocks of data, so I only need to find a block (they are delimited by magic bits), then create a temporary one-block bzip2 file from it in memory, and finally pass that to the bz2.decompress function. Easy, no? The bzip2 format has a crc32 checksum for the file at the end. No problem, binascii.crc32 to the rescue. But wait. The data to be checksummed does not necessarily end on a byte boundary, and the crc32 function operates on a whole number of bytes. My plan: use the binascii.crc32 function on all but the last byte, and then a function of my own to update the computed crc with the last 1-7 bits. But hours of coding and testing has left me bewildered, and my puzzlement can be boiled down to this question: how come crc32("\x00") is not 0x00000000? Shouldn't it be, according to the wikipedia article? You start with 0b00000000 and pad with 32 0's, then do polynomial division with 0x04C11DB7 until there are no ones left in the first 8 bits, which is immediately. Your last 32 bits is the checksum, and how can that not be all zeroes? I've searched google for answers and looked at the code of several crc32 implementations without finding any clue to why this is so.

  Read the article

• computes the number of possible orderings of n objects under the relations < and =

  - by hilal

  Here is the problem : Give a algorithm that takes a positive integer n as input, and computes the number of possible orderings of n objects under the relations < and =. For example, if n = 3 the 13 possible orderings are as follows: a = b = c, a = b < c, a < b = c, a < b < c, a < c < b, a = c < b, b < a = c, b < a < c, b < c < a, b = c < a, c < a = b, c < a < b, c < b < a. Your algorithm should run in time polynomial in n. I'm null to this problem. Can you find any solution to this dynamic-programming problem?

  Read the article

• linked list printing using while loop and combining like terms

  - by C Z

  i have a problem printing out my linked list. My program asks the user to enter many different coefficients and degrees and makes it a polynomial and using mergesort it sorts it and then prints it, now i want to combine like terms and i have a problem doing so. thats part of my function that i don't know what is wrong with it: Term* p; p=poly; if (p==0) cout<<"---empty list---"; while(p !=0) if (p->coef==(p->next)->coef){ cout<<(p->deg)+((p->next)->deg)<<"x^"<<(p->coef)<<endl; p=p->next;} if (p->coef !=(p->next)->coef){ cout<<p->deg<<"x"<<p->coef<<"+"; p=p->next;} cout<<endl; } and thats my struct: struct Term { int deg; float coef; Term *next; }; typedef Term* Poly;

  Read the article

• Diophantine Equation [closed]

  - by ANIL

  In mathematics, a Diophantine equation (named for Diophantus of Alexandria, a third century Greek mathematician) is a polynomial equation where the variables can only take on integer values. Although you may not realize it, you have seen Diophantine equations before: one of the most famous Diophantine equations is: X^n+Y^n=Z^n We are not certain that McDonald's knows about Diophantine equations (actually we doubt that they do), but they use them! McDonald's sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 nuggets, since no non- negative integer combination of 6's, 9's and 20's adds up to 16. To determine if it is possible to buy exactly n McNuggets, one has to solve a Diophantine equation: find non-negative integer values of a, b, and c, such that 6a + 9b + 20c = n. Problem 1 Show that it is possible to buy exactly 50, 51, 52, 53, 54, and 55 McNuggets, by finding solutions to the Diophantine equation. You can solve this in your head, using paper and pencil, or writing a program. However you chose to solve this problem, list the combinations of 6, 9 and 20 packs of McNuggets you need to buy in order to get each of the exact amounts. Given that it is possible to buy sets of 50, 51, 52, 53, 54 or 55 McNuggets by combinations of 6, 9 and 20 packs, show that it is possible to buy 56, 57,..., 65 McNuggets. In other words, show how, given solutions for 50-55, one can derive solutions for 56-65. Problem 2 Write an iterative program that finds the largest number of McNuggets that cannot be bought in exact quantity. Your program should print the answer in the following format (where the correct number is provided in place of n): "Largest number of McNuggets that cannot be bought in exact quantity: n" Hints: Hypothesize possible instances of numbers of McNuggets that cannot be purchased exactly, starting with 1 For each possible instance, called n, a. Test if there exists non-negative integers a, b, and c, such that 6a+9b+20c = n. (This can be done by looking at all feasible combinations of a, b, and c) b. If not, n cannot be bought in exact quantity, save n When you have found six consecutive values of n that in fact pass the test of having an exact solution, the last answer that was saved (not the last value of n that had a solution) is the correct answer, since you know by the theorem that any amount larger can also be bought in exact quantity

  Read the article

• Faster Matrix Multiplication in C#

  - by Kyle Lahnakoski

  I have as small c# project that involves matrices. I am processing large amounts of data by splitting it into n-length chunks, treating the chucks as vectors, and multiplying by a Vandermonde** matrix. The problem is, depending on the conditions, the size of the chucks and corresponding Vandermonde** matrix can vary. I have a general solution which is easy to read, but way too slow: public byte[] addBlockRedundancy(byte[] data) { if (data.Length!=numGood) D.error("Expecting data to be just "+numGood+" bytes long"); aMatrix d=aMatrix.newColumnMatrix(this.mod, data); var r=vandermonde.multiplyBy(d); return r.ToByteArray(); }//method This can process about 1/4 megabytes per second on my i5 U470 @ 1.33GHz. I can make this faster by manually inlining the matrix multiplication: int o=0; int d=0; for (d=0; d<data.Length-numGood; d+=numGood) { for (int r=0; r<numGood+numRedundant; r++) { Byte value=0; for (int c=0; c<numGood; c++) { value=mod.Add(value, mod.Multiply(vandermonde.get(r, c), data[d+c])); }//for output[r][o]=value; }//for o++; }//for This can process about 1 meg a second. (Please note the "mod" is performing operations over GF(2^8) modulo my favorite irreducible polynomial.) I know this can get a lot faster: After all, the Vandermonde** matrix is mostly zeros. I should be able to make a routine, or find a routine, that can take my matrix and return a optimized method which will effectively multiply vectors by the given matrix, but faster. Then, when I give this routine a 5x5 Vandermonde matrix (the identity matrix), there is simply no arithmetic to perform, and the original data is just copied. ** Please note: What I use the term "Vandermonde", I actually mean an Identity matrix with some number of rows from the Vandermonde matrix appended (see comments). This matrix is wonderful because of all the zeros, and because if you remove enough rows (of your choosing) to make it square, it is an invertible matrix. And, of course, I would like to use this same routine to convert any one of those inverted matrices into an optimized series of instructions. How can I make this matrix multiplication faster? Thanks! (edited to correct my mistake with Vandermonde matrix)

  Read the article

• Partial overriding in Java (or dynamic overriding while overloading)

  - by Lie Ryan

  If I have a parent-child that defines some method .foo() like this: class Parent { public void foo(Parent arg) { System.out.println("foo in Function"); } } class Child extends Parent { public void foo(Child arg) { System.out.println("foo in ChildFunction"); } } When I called them like this: Child f = new Child(); Parent g = f; f.foo(new Parent()); f.foo(new Child()); g.foo(new Parent()); g.foo(new Child()); the output is: foo in Parent foo in Child foo in Parent foo in Parent But, I want this output: foo in Parent foo in Child foo in Parent foo in Child I have a Child class that extends Parent class. In the Child class, I want to "partially override" the Parent's foo(), that is, if the argument arg's type is Child then Child's foo() is called instead of Parent's foo(). That works Ok when I called f.foo(...) as a Child; but if I refer to it from its Parent alias like in g.foo(...) then the Parent's foo(..) get called irrespective of the type of arg. As I understand it, what I'm expecting doesn't happen because method overloading in Java is early binding (i.e. resolved statically at compile time) while method overriding is late binding (i.e. resolved dynamically at compile time) and since I defined a function with a technically different argument type, I'm technically overloading the Parent's class definition with a distinct definition, not overriding it. But what I want to do is conceptually "partially overriding" when .foo()'s argument is a subclass of the parent's foo()'s argument. I know I can define a bucket override foo(Parent arg) in Child that checks whether arg's actual type is Parent or Child and pass it properly, but if I have twenty Child, that would be lots of duplication of type-unsafe code. In my actual code, Parent is an abstract class named "Function" that simply throws NotImplementedException(). The children includes "Polynomial", "Logarithmic", etc and .foo() includes things like Child.add(Child), Child.intersectionsWith(Child), etc. Not all combination of Child.foo(OtherChild) are solvable and in fact not even all Child.foo(Child) is solvable. So I'm best left with defining everything undefined (i.e. throwing NotImplementedException) then defines only those that can be defined. So the question is: Is there any way to override only part the parent's foo()? Or is there a better way to do what I want to do?

  Read the article

• Matlab wont extract first row & column because of matrix dimensions !

  - by ZaZu

  Hey guys, I am tracking an object that is thrown in air, and this object governs a parabolic pattern. Im tracking the object through a series of 30 images. I managed to exclude all the background and keep the object apparent, then used its centroid to get its coordinates and plot them. Now im supposed to predict where the object is going to fall, so I used polyfit & polyval .. the problem is, matlab says ??? Index exceeds matrix dimensions. Now the centroid creates its own structure with a row and 2 columns. Everytime the object moves in the loop, it updates the first row only .. Here is part of the code : For N=1:30 . . . x=centroid(1,1); % extract first row and column for x y=centroid(1,2); % extract secnd row and column for x plot_xy=plot(x,y) set(plot_xy,'XData',x(1:N),'YData',y(1:N)); fitting=polyfit(x(1:N),y(1:N),2); parabola=plot(x,nan(23,1)); evaluate=polyval(fitting,x); set(parabola,'YData',evaluate) . . end The error message I get is ??? Index exceeds matrix dimensions. It seems that (1:N) is causing the problems .. I honestly do not know why .. But when I remove N, the object is plotted along with its points, but polyfitting wont work, it gives me an error saying : Warning: Polynomial is not unique; degree >= number of data points. > In polyfit at 72 If I made it (1:N-1) or something, it plots more points before it starts giving me the same error (not unique ...) . Any ideas why ?? Thanks alot !!

  Read the article

• Calculate the number of ways to roll a certain number

  - by helloworld

  I'm a high school Computer Science student, and today I was given a problem to: Program Description: There is a belief among dice players that in throwing three dice a ten is easier to get than a nine. Can you write a program that proves or disproves this belief? Have the computer compute all the possible ways three dice can be thrown: 1 + 1 + 1, 1 + 1 + 2, 1 + 1 + 3, etc. Add up each of these possibilities and see how many give nine as the result and how many give ten. If more give ten, then the belief is proven. I quickly worked out a brute force solution, as such int sum,tens,nines; tens=nines=0; for(int i=1;i<=6;i++){ for(int j=1;j<=6;j++){ for(int k=1;k<=6;k++){ sum=i+j+k; //Ternary operators are fun! tens+=((sum==10)?1:0); nines+=((sum==9)?1:0); } } } System.out.println("There are "+tens+" ways to roll a 10"); System.out.println("There are "+nines+" ways to roll a 9"); Which works just fine, and a brute force solution is what the teacher wanted us to do. However, it doesn't scale, and I am trying to find a way to make an algorithm that can calculate the number of ways to roll n dice to get a specific number. Therefore, I started generating the number of ways to get each sum with n dice. With 1 die, there is obviously 1 solution for each. I then calculated, through brute force, the combinations with 2 and 3 dice. These are for two: There are 1 ways to roll a 2 There are 2 ways to roll a 3 There are 3 ways to roll a 4 There are 4 ways to roll a 5 There are 5 ways to roll a 6 There are 6 ways to roll a 7 There are 5 ways to roll a 8 There are 4 ways to roll a 9 There are 3 ways to roll a 10 There are 2 ways to roll a 11 There are 1 ways to roll a 12 Which looks straightforward enough; it can be calculated with a simple linear absolute value function. But then things start getting trickier. With 3: There are 1 ways to roll a 3 There are 3 ways to roll a 4 There are 6 ways to roll a 5 There are 10 ways to roll a 6 There are 15 ways to roll a 7 There are 21 ways to roll a 8 There are 25 ways to roll a 9 There are 27 ways to roll a 10 There are 27 ways to roll a 11 There are 25 ways to roll a 12 There are 21 ways to roll a 13 There are 15 ways to roll a 14 There are 10 ways to roll a 15 There are 6 ways to roll a 16 There are 3 ways to roll a 17 There are 1 ways to roll a 18 So I look at that, and I think: Cool, Triangular numbers! However, then I notice those pesky 25s and 27s. So it's obviously not triangular numbers, but still some polynomial expansion, since it's symmetric. So I take to Google, and I come across this page that goes into some detail about how to do this with math. It is fairly easy(albeit long) to find this using repeated derivatives or expansion, but it would be much harder to program that for me. I didn't quite understand the second and third answers, since I have never encountered that notation or those concepts in my math studies before. Could someone please explain how I could write a program to do this, or explain the solutions given on that page, for my own understanding of combinatorics? EDIT: I'm looking for a mathematical way to solve this, that gives an exact theoretical number, not by simulating dice

  Read the article

< Previous Page | 1 2 3 4