# Thread: For the math nerds...

1. ## Re: For the math nerds...

@Warren Hill: looking at your post it dawns on me that if there are N factors there are 2^N divisors to test (with likely many duplicates, but I don't care) and the binary form of the value iterated from 0 to 2^N-1makes it easy to compute the divisor... And if you take this value as path in a binary tree, and set the node value to the corresponding divisor, you can cut off everything beyond the nodes where the divisor is greater than the square root.

@trent.josephsen: yes, alas

@Bachstelze: everything is easier with the right library but yes, iterating the divisors is likely the best solution (see above)

@Vaphell: nice awk hack!

@spjackson: yes, this limits the number of divisors to check (or to compute)
Last edited by ofnuts; January 16th, 2013 at 11:25 PM.

2. ## Re: For the math nerds...

Sorry you are correct I am missing a few 5s

If we take total pixels P = 480000 for example

Then in C

int x,y;
Code:
for (x = sqrt(P); x > 0; x--){
y = P / x;
if (x * y == P){
printf( "Possible solutions %d x %d, and %d x %d \n", x, y, y,x);
}
}
Is probably the simplest and while it may not be the fastest. It should be fast enough for images where the total number of pixels is less than a few million on most computers
Last edited by Warren Hill; January 17th, 2013 at 09:22 AM.

3. ## Re: For the math nerds...

Code:
y = P / x;
if (x * y == P)...
dont we have % for that?
otherwise i agree it's not worth the effort to think much about this problem, unless for mental gymnastics. Complexity of sqrt(n) nets you 10^6 operations for 10^12 magnitude input and that is what, less than a second of cpu time?
Last edited by Vaphell; January 17th, 2013 at 03:20 PM.

4. ## Re: For the math nerds...

True

if ( x * y == P)

if (x % y ==0)

or

if (!(x % y))

also works and may be slightly quicker, if less easy to understand

5. Gee! These Aren't Roasted!
Join Date
Dec 2012
Beans
172

## Re: For the math nerds...

PHP Code:
from math import sqrt
def find_wh
(n):

sqrt_n int(sqrt(n))
for
w in range(sqrt_n0, -1):

hremainder divmod(nw)

ratio float(h) / w

if remainder == and ratio >= and ratio <= 2:
print
h

6. 5 Cups of Ubuntu
Join Date
Jun 2006
Location
Knoxville, TN (USA)
Beans
24
Distro
Ubuntu 10.10 Maverick Meerkat

## Re: For the math nerds...

Searching for two factors close to the square root of N is the strength of Fermat's factoring method.

Where trial division starts small and goes up (at least typically), Fermat's method starts with the first square a^2 greater than or equal to N and checks if a^2 - N happens to be another square b^2. If so, then N = a^2 - b^2 = (a+b)(a-b) and we have our most nearly equal factors of N.

If that fails, increment a, etc. and test again, until a factorization is found or a reaches (N-1)/2, after which point if N is odd we find:

[(N+1)/2]^2 - N = [(N-1)/2]^2

implying the trivial factorization N = N*1.

In practice here we would stop once (a+b)/(a-b) exceeds the allowable aspect ratio, e.g. 2.
Last edited by hardmath; May 26th, 2013 at 04:14 AM. Reason: To add stopping criterion

7. ## Re: For the math nerds...

Thanks for the tip...

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•