Thread: [algorithm] Iterate through the product of two numbers

  1. #1
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445

    [algorithm] Iterate through the product of two numbers

    I need to iterate (from largest to smallest) through the products of two numbers. At first thought this would be as easy as:

    Code:
    int a = 4;
    int b = 4;
    int c = 0;
    
    for(; a > 0; a--) {
        for(; b > 0; b--) {
            c = a * b;
        }
        b = 4;
    }
    Forgetting for a moment the problem of repeated products, it won't work. As the code runs you will realize the inner loop will compromise the order. Here's the output of the products (duplicates removed for clarity):

    16 12 8 4 9 6 3 2 1
    I'm not concerned at the issue of repeated products. For my purposes, that won't add any significant weight. I'm however eager to listen to any ideas on how to iterate orderly through the product of two numbers.

    Note: You will be correct if you assume I know nothing about the terms of the product. The algorithm can be feed with any kind of terms.
    Last edited by Mario F.; 11-05-2014 at 02:26 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    Is it out of the question to generate the data and then sort it for output?
    What can this strange device be?
    When I touch it, it gives forth a sound
    It's got wires that vibrate and give music
    What can this thing be that I found?

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445
    Quote Originally Posted by Elkvis View Post
    Is it out of the question to generate the data and then sort it for output?
    Yeah. No sort should be performed.

    EDIT: I'm mulling over the idea of looking at the product as a series of sums (which if what it is). But I'm not sure yet how to put that into practice.
    Last edited by Mario F.; 11-05-2014 at 02:23 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Okay, so it seems to me like you're looking for all product pairs of, for example, integers 1 to 4.

    In grid form, the products can be written as

    16 12 8 4
    12 9 6 3
    8 6 4 2
    4 3 2 1

    Notice that there is diagonal with a mirrored side?

    This then leaves the triangle :

    16
    12 9
    8 6 4
    4 3 2 1

    I'm not sure how to translate all this into code but that's a pre-sorted way of computing product pairs.

    Edit :

    This works (kind of). Okay, it doesn't.

    Code:
    #include <iostream>
    
    
    int main(void)
    {
        const int a = 4, 
                  b = a;
    
    
        int prev = 0;
    
    
        for (int i = 0 ; i < a; ++i)
        {
            for (int j = 0; j < i + 1; ++j)
            {
                const int prod = (a - i) * (b - j);
    
    
                if (prod == prev)
                    continue;
    
    
                prev = prod;
    
    
                std::cout << prod << std::endl;
            }
        }
    
    
        return 0;
    }
    Last edited by MutantJohn; 11-05-2014 at 03:24 PM.

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    [Edit]
    *sigh*

    Nevermind. I was being silly about the condition for multipliers.
    [/Edit]

    Soma
    Last edited by phantomotap; 11-05-2014 at 03:49 PM.
    Salem Was Wrong! -- Pedant Necromancer
    Four isn't random! -- Gibbering Mouther

  6. #6
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    (Note: I don't know the answer yet, but I want to try and help solve it in a way that would let others see how one can proceed with a problem like this.)

    Let's see what the product lists look like. Since duplicates are discarded anyway, we can assume a ≥ b due to multiplication being commutative:
    Code:
    a │ b │ List of products
    ──┼───┼──────────────────────────────────────────────────────────────────────────
    1 │ 1 │ 11
      ┊   ┊
    2 │ 1 │ 21, 11
    2 │ 2 │ 22, 21, 11
      ┊   ┊
    3 │ 1 │ 31, 21, 11
    3 │ 2 │ 32, 22, 31, 21, 11
    3 │ 3 │ 33, 32, 22/41, 31, 21, 11
      ┊   ┊
    4 │ 1 │ 41, 31, 21, 11
    4 │ 2 │ 42, 32, 22/41, 31, 21, 11
    4 │ 3 │ 43, 33, 42, 32, 22/41, 31, 21, 11
    4 │ 4 │ 44, 43, 33, 42, 32, 22/41, 31, 21, 11
      ┊   ┊
    5 │ 1 │ 51, 41, 31, 21, 11
    5 │ 2 │ 52, 42, 32, 51, 22/41, 31, 21, 11
    5 │ 3 │ 53, 43, 52, 33, 42, 32, 51, 22/41, 31, 21, 11
    5 │ 4 │ 54, 44, 53, 43, 52, 33, 42, 32, 51, 22/41, 31, 21, 11
    5 │ 5 │ 55, 54, 44, 53, 43, 52, 33, 42, 32, 51, 22/41, 31, 21, 11
      ┊   ┊
    A brute force approach would be similar to selection sort, albeit without saving any of the values. A nave implementation of that would be a quadruple loop.

    My intuition () says the above table looks like there must be a simple-ish algorithm for this, but I don
    t trust the table to be large enough to get a clear/reliable picture. Also, I didn't verify the above table -- I should have used e.g. an awk script to generate it instead.

    I'll run with my intuition here for now. (But remember, I don't know yet, so I might be wrong.)

    Let's start with a clear starting point, say aa. We don't pick the obvious next highest product (a(a-1)), but instead use a loop or something to find all the products larger than (a-1)(a-1). If we can do this, then we can start with however large an a, and just repeat this until we get down to 22 .

    If we start with ab with a>b, we can just generate ab, (a-1)b, (a-2)b, down to bb.

    The subproblem is still left unsolved:

    How to find all products (in descending order of value) cd, such that aa > cd > (a-1)(a-1), with c≤a and d<a?

    I think this point is a really good spot to ask a colleague for insights. Anybody?

    Edited to add: [STRIKE]The nested loop brute force search for the subproblem is rather obvious, so that means this approach should yield a triple loop solution directly. Anything better?[/STRIKE] Oh, that won't give them in the correct order if there are more than one.
    Last edited by Nominal Animal; 11-05-2014 at 04:19 PM.

  7. #7
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by MutantJohn View Post
    In grid form
    You may be onto something there. If you think of an integer grid (or Cartesian coordinates),
    Code:
    6│ 6 12 18 24 30 36
    5│ 5 10 15 20 25 30
    4│ 4  8 12 16 20 24
    3│ 3  6  9 12 15 18
    2│ 2  4  6  8 10 12
    1│ 1  2  3  4  5  6
    ─┼──────────────────
     │ 1  2  3  4  5  6
    then the product at each point is just the distance squared to origin. Duplicate values are on the exact same circle. Due to symmetries, you can consider just the upper or lower antidiagonal triangle.

    The product list for a>b is just ab, (a-1)b, (a-2)b, down to bb, plus the non-duplicate distances squared in an octant like in the above graph.

    There sure is a way to traverse the points in the above octant in increasing (or decreasing) distance to origin, but what is it?
    Last edited by Nominal Animal; 11-05-2014 at 05:25 PM.

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Going for simplicity here. And I haven't read the lengthier posts in detail, so forgive me if I repeat anything, but can you use something akin to the Sieve of Eratosthenes? Generate and store all possible products, then walk the sieve (bit-packed array) backwards. This is still O(n**2), but should cover repeated products and ordering. In thoroughly untested and hastily thought-out pseudo code
    Code:
    all_products(int a, int b)
        int max_product = a * b;
        for (i = 1; i <= max(a, b))
            for (n = i; n <= max_product; n += i)
                mark n as a product in your sieve
    
        walk the sieve from max_product down to 1, outputting valid products
    EDIT: That's what I get for rushing. I was thinking I was going to get back to work, but this is too interesting. The above doesn't work. However if you take the naive nested loop strategy (in Mario's post #1), and use a bit-mapped array to store valid products, you can easily walk that backwards to get your list.
    Last edited by anduril462; 11-05-2014 at 07:54 PM.

  9. #9
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Well, the following triple loop seems to work, but I don't think it is the best we could do...

    Code:
    all_products(a, b):
    
        /* Optional sanity check! */
        if a < 1 or b < 1:
            return /* nothing to do */
    
        /* Make sure a >= b. */
        if b > a:
            c = a
            a = b
            b = c
    
        /* Highest possible product. */
        best_a = a
        best_b = b
        best   = a * b
    
        /* Outermost loop */
        while best > 1:
            emit best
    
            last = best
            best = 0
    
            /* Check all distances squared in the triangle (1,1)-(a,1)-(a,a). */
    
            test_a = a
            while test_a > 0:
    
                if test_a > b:
                    test_b = b
                else:
                    test_b = test_a
                test = test_a * test_b
    
                /* No need to test known smaller products. */
                if test < best:
                    break
    
                /* Exclude too large test_b's */
                if test >= last:
                    test_b = (last - 1) / test_a  /* Round towards zero! */
                    test   = test_a * test_b
    
                while test > best:
                    best_a = test_a
                    best_b = test_b
                    best   = test
                    test_b = test_b - 1
                    test   = test - test_a   /* test = test_a * test_b */
    
                test_a = test_a - 1
    
        /* Only the final product left. */
        emit 1
    For 16,9 this emits
    Code:
    144 135 128 126 120 117 112 108 105 104 99 98 96 91 90 88 84 81 80 78 77 75 72 70 66 65 64 63 60 56 55 54 52 50 49 48 45 44 42 40 39 36 35 33 32 30 28 27 26 25 24 22 21 20 18 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
    which should be correct.

  10. #10
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445
    What we are looking here is some function f(x,y) that describes the progression. MutantJohn seems to have provided a starting framework. Where there is a pattern, there is a mathematical way to describe that pattern.

    I'm on my way to work and I can't tackle this now, but I will later tonight. If and when that function is found, it is "just" a matter of proving it for all terms and we should have a solution.

    EDIT: Some tips for anyone having the time to deal with it. Research arithmetic progressions, the binomial coeficient, the gamma function, and look into factorials as a possible way to describe the products since most products of successive integers can be described by some combination of factorials.
    Last edited by Mario F.; 11-06-2014 at 01:40 AM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    Just out of curiosity, why descending order, and why no duplicates? What is this for? Do you have any particular application(s) in mind?

  12. #12
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445
    Quote Originally Posted by anduril462 View Post
    Just out of curiosity, why descending order, and why no duplicates? What is this for? Do you have any particular application(s) in mind?
    There's no problem with duplicates. I don't think they add too much weight to the algorithm. Descending order because I merely guessed this could bring further complications. If that is the case, one could derive the ascending order algorithm more easily from a more complicated one, than the other way around.

    There will be two algorithms, so that there won't be a significant loss in response time, if one requires larger or smaller products first.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  13. #13
    Registered User
    Join Date
    Mar 2011
    Posts
    596
    Can't you just step through all values, 1 to x*y ( or x*y to 1),
    and test that each value is evenly divisible by x and also evenly divisible by y?

    (edited)
    Well that was wrong; it should be "test that each value is equal to product of any values of x and y

    -
    Last edited by megafiddle; 11-06-2014 at 02:29 PM.

  14. #14
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,907
    This is the best I could come up with:
    In pseudo code
    Code:
    max_product = a * b
    for all values from max_product down to 1
        if it can be broken down into two factors, one of which is <= a and the other of which is <= b
            print it out
    And implemented in C
    Code:
    void all_products_via_factors(int a, int b)
    {
        int max_product = a * b;
        if (b < a) {
            int temp = b;
            b = a;
            a = temp;
        }
        for (int i = max_product; i >= 1; i--) {
            for (int j = b; j >= 1; j--) {
                if ((i % j == 0) && ((int) ((double) i / j)) <= a) {
                    printf("%d ", i);
                    break;
                }
            }
        }
    }
    I implemented my sieve and Nominal Animal's version as well for comparison. I ran the following
    Code:
    $ for a in {1..25}; do for b in {1..29}; do for p in sieve nominal factor; do echo -n "${a} ${b}: " >> ${p}.txt; ./${p} ${a} ${b} >> ${p}.txt; done; done; done
    $ diff sieve.txt nominal.txt 
    $ diff sieve.txt factor.txt
    All 3 versions produced the same output.
    Last edited by anduril462; 11-06-2014 at 02:46 PM.

  15. #15
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Angola
    Posts
    8,445
    Quote Originally Posted by megafiddle View Post
    Can't you just step through all values, 1 to x*y ( or x*y to 1)
    I'm hoping for a more efficient way. Some form that allows me to traverse the actual products without many cycles being wasted.

    EDIT: I think I'm close to a solution. Need just more time to deal with some minor (hopefully) errors.
    Last edited by Mario F.; 11-06-2014 at 04:33 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 08-30-2012, 02:51 PM
  2. the algorithm used in c++ to generate random numbers
    By karim tarbali in forum C++ Programming
    Replies: 7
    Last Post: 02-17-2012, 08:01 AM
  3. Amicable numbers efficient algorithm?
    By Andi Rrashi in forum C Programming
    Replies: 15
    Last Post: 11-04-2011, 06:02 PM
  4. Help With Algorithm Egyptian Numbers
    By zerlok in forum C++ Programming
    Replies: 2
    Last Post: 02-23-2009, 08:57 AM
  5. Replies: 8
    Last Post: 09-11-2006, 11:26 AM