Page 2 of 2 FirstFirst 12
Results 11 to 17 of 17

Thread: For the math nerds...

  1. #11
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,801
    Distro
    Kubuntu 12.10 Quantal Quetzal

    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. #12
    Join Date
    Sep 2012
    Location
    UK
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    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. #13
    Join Date
    Jul 2007
    Location
    Poland
    Beans
    4,243
    Distro
    Ubuntu 10.04 Lucid Lynx

    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.
    if your question is answered, mark the thread as [SOLVED]. Thx.
    To post code or command output, use [code] tags.
    Check your bash script here // BashFAQ // BashPitfalls

  4. #14
    Join Date
    Sep 2012
    Location
    UK
    Beans
    Hidden!
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: For the math nerds...

    True

    Instead of

    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. #15
    iMac71 is offline 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. #16
    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. #17
    Join Date
    Aug 2011
    Location
    47°9′S 126°43W
    Beans
    1,801
    Distro
    Kubuntu 12.10 Quantal Quetzal

    Re: For the math nerds...

    Thanks for the tip...

Page 2 of 2 FirstFirst 12

Bookmarks

Posting Permissions

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