Algorithm to pick values from array that sum closest to a target value?
This problem is known as the subset sum problem, which is a special case of the Knapsack problem. Wikipedia is a good starting point for some algorithms.
math
Convert Latitude and Longitude to point in 3D space
I’ve reformatted the code that was previously mentioned here, but more importantly you have left out some of the equations mentioned in the link provided by Niklas R def LLHtoECEF(lat, lon, alt): # see http://www.mathworks.de/help/toolbox/aeroblks/llatoecefposition.html rad = np.float64(6378137.0) # Radius of the Earth (in meters) f = np.float64(1.0/298.257223563) # Flattening factor WGS84 Model cosLat = … Read more
Finding square root without using sqrt function?
There is a better algorithm, which needs at most 6 iterations to converge to maximum precision for double numbers: #include <math.h> double sqrt(double x) { if (x <= 0) return 0; // if negative number throw an exception? int exp = 0; x = frexp(x, &exp); // extract binary exponent from x if (exp & … Read more
Integer division in Java [duplicate]
They are being divided in integer arithmetics. So dividing integer a by integer b you get how many times b fits into a. Also a % b will give you a remainder of a division. So (a / b ) * b + a % b = a
counting combinations and permutations efficiently
if n is not far from r then using the recursive definition of combination is probably better, since xC0 == 1 you will only have a few iterations: The relevant recursive definition here is: nCr = (n-1)C(r-1) * n/r This can be nicely computed using tail recursion with the following list: [(n – r, 0), … Read more
Area of rectangle-rectangle intersection
Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides. The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). … Read more
Fastest way to get the integer part of sqrt(n)?
I would try the Fast Inverse Square Root trick. It’s a way to get a very good approximation of 1/sqrt(n) without any branch, based on some bit-twiddling so not portable (notably between 32-bits and 64-bits platforms). Once you get it, you just need to inverse the result, and takes the integer part. There might be … Read more
Javascript Math Error: Inexact Floats [duplicate]
Floating point value is inexact. This is pretty much the answer to the question. There is finite precision, which means that some numbers can not be represented exactly. Some languages support arbitrary precision numeric types/rational/complex numbers at the language level, etc, but not Javascript. Neither does C nor Java. The IEEE 754 standard floating point … Read more
How sqrt() of GCC works after compiled? Which method of root is used? Newton-Raphson?
yeah, I know fsqrt. But how the CPU does it? I can’t debug hardware Typical div/sqrt hardware in modern CPUs uses a power of 2 radix to calculate multiple result bits at once. e.g. http://www.imm.dtu.dk/~alna/pubs/ARITH20.pdf presents details of a design for a Radix-16 div/sqrt ALU, and compares it against the design in Penryn. (They claim … Read more
Fast divisibility tests (by 2,3,4,5,.., 16)?
In every case (including divisible by 2): if (number % n == 0) do(); Anding with a mask of low order bits is just obfuscation, and with a modern compiler will not be any faster than writing the code in a readable fashion. If you have to test all of the cases, you might improve … Read more