User mathmonkey - MathOverflow

Enumerating ways to decompose an integer into the sum of two squares

2010-06-26T22:05:28Z

The well known "Sum of Squares Function" tells you the number of ways you can represent an integer as the sum of two squares. See the link for details, but it is based on counting the factors of the number N into powers of 2, powers of primes = 1 mod 4 and powers of primes = 3 mod 4.

Given such a factorization, it's easy to find the number of ways to decompose N into two squares. But how do you efficiently enumerate the decompositions?

So for example, given N=2*5*5*13*13=8450 , I'd like to generate the four pairs:

13*13+91*91=8450

23*23+89*89=8450

35*35+85*85=8450

47*47+79*79=8450

The obvious algorithm (I used for the above example) is to simply take i=1,2,3,...,$\sqrt{N/2}$ and test if (N-i*i) is a square. But that can be expensive for large N. Is there a way to generate the pairs more efficiently? I already have the factorization of N, which may be useful.

(You can instead iterate between $i=\sqrt{N/2}$ and $\sqrt{N}$ but that's just a constant savings, it's still $O(\sqrt N)$.

Robust black box function minimization with extremely expensive cost function

2010-08-27T21:16:04Z

There is an enormous amount of information about the common applied math problem of minimizing a function.. software packages, hundreds of books, research, etc. But I still have not found a good reference for the case where the function to be sampled is extremely expensive.

My specific problem is an applied one of computer science, where I have a simulation which has databases with a dozen parameters that affect voxel sizes, cache distribution, tree branching, etc. These numeric parameters don't affect the algorithm correctness, just runtime. I want to minimize runtime.

Thus, I can treat the problem like a black box minimization. My cost function is runtime, which I want to minimize. I don't have derivatives, and I can treat it like a black box. I have a decent starting point and even rough scales of each parameter. There can be interations and correlations between parameters and even noise in time measurements (luckily small.)

So why not just throw this into a standard least-squares minimization tool, using any package out there? Because my timing samples each take 8 hours to run.. so each data point is precious, and the algorithms I find tend to ignore this cost. A classic Levenberg-Marquand procedure freely "spends" samples and doesn't even remember the full history of each sample taken (instead updating some average statistics).

So my question is to ask for a pointer to iterative function minimization methods which use the minimum number of samples of the function. Ideally it would work where I could pass in a set of already-sampled locations and the value at each location, and the algorithm would spit out a single new location to take the next sample (which may be an exploratory sample, not a guess at a best minimum location, if the algorithm thinks it's worthwhile to test.)

I can likely take hundreds of samples, but only hundreds, and most multidimensional minimization methods expect to take millions.

Currently I am doing doing the minimization manually daily, using my own ad-hoc invention. I have say 40 existing timing samples to my 15-parameter model. I fit all my existing samples to a sum of independent quadratics (making the big initial assumption that each parameter is independent) then look at each of the N*(N-1)/2 ~=100 possible correlation coefficients of the full quadratic matrix. I find the few single matrix entries that when allowed to change from 0.0, give the best quadratic fit to my data, and allow those few entries to be their best least-squares fit. I also give locations with small (faster) values higher weight in the fit (a bit ad hoc, but useful to throw out behavior distant from the minimum) Once I have this matrix, I manually look at graphs in each of the major eigenvalue directions and eyeball locations which seem to need better sampling. I recombine all these guesses back into a new sample location. Each day, I tend to generate 4 new points, set up a run to test them over the next day, and repeat the whole thing again after the computation is done. Weekends get 10 point batches!

Thanks for any ideas! This question likely doesn't have a perfect "best" answer but I'm stuck at what strategy would work best when the evaluation cost is so huge.

Efficient quadratic residue mod 2^32

2010-07-19T06:36:04Z

I want to determine if a value is a quadratic residue mod $2^{32}$. I've developed a very fast pre-screening method based on a Bloom Filter that identifies quadratic residues for mod $2^7=128$ in just a couple multiplies, but it can't extend to much higher powers efficiently.

The general method of testing for quadratic residues will work, using Hensel lifting to find a modular square root if it exists, but I wonder if there are any shortcuts given the specific modulus of $2^{32}$.

This is for a computer search, so efficiency using 32 or 64 bit math helps.

Comment by MathMonkey

2010-07-19T16:07:15Z

Robin, that sounds like it's quite computable! Could you add that as an answer so we can vote and discuss it? What's the logic or derivation behind that conclusion?

Comment by MathMonkey

2010-06-27T02:53:29Z

And finally, is it guaranteed that the above algorithm will actually find ALL of the top level N decompositions? The formula just tells us that given one factoring we get one sum of two squares decompositions, but does that mean that all factorings will give us all decompositions?

Comment by MathMonkey

2010-06-27T02:50:40Z

So what would the algorithm itself be? It sounds like I should enumerate all possible $xy=N$ factorings (both prime and composite). Then for each, decompose $x$ into each possible $a^2+b^2$ and each y into each possible $c^2+d^2$, and use the above formula to find one answer to the top level N decomposition. Finally after iterating over all such factors, and over the two inner loops of all decompositions of those factors, I should take all the answers and sort them and eliminate duplicates. Is this the right algorithm or is it doing unnecessary work?