[algorithm] Iterate through the product of two numbers

[Mario F.]

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

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.

[Elkvis]

Is it out of the question to generate the data and then sort it for output?

[Mario F.]

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.

[MutantJohn]

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.

#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;
}

[phantomotap]

O_o

[Edit]
*sigh*

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

Soma

[Nominal Animal]

(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:

a │ b │ List of products
──┼───┼──────────────────────────────────────────────────────────────────────────
1 │ 1 │ 1·1
  ┊   ┊
2 │ 1 │ 2·1, 1·1
2 │ 2 │ 2·2, 2·1, 1·1
  ┊   ┊
3 │ 1 │ 3·1, 2·1, 1·1
3 │ 2 │ 3·2, 2·2, 3·1, 2·1, 1·1
3 │ 3 │ 3·3, 3·2, 2·2/4·1, 3·1, 2·1, 1·1
  ┊   ┊
4 │ 1 │ 4·1, 3·1, 2·1, 1·1
4 │ 2 │ 4·2, 3·2, 2·2/4·1, 3·1, 2·1, 1·1
4 │ 3 │ 4·3, 3·3, 4·2, 3·2, 2·2/4·1, 3·1, 2·1, 1·1
4 │ 4 │ 4·4, 4·3, 3·3, 4·2, 3·2, 2·2/4·1, 3·1, 2·1, 1·1
  ┊   ┊
5 │ 1 │ 5·1, 4·1, 3·1, 2·1, 1·1
5 │ 2 │ 5·2, 4·2, 3·2, 5·1, 2·2/4·1, 3·1, 2·1, 1·1
5 │ 3 │ 5·3, 4·3, 5·2, 3·3, 4·2, 3·2, 5·1, 2·2/4·1, 3·1, 2·1, 1·1
5 │ 4 │ 5·4, 4·4, 5·3, 4·3, 5·2, 3·3, 4·2, 3·2, 5·1, 2·2/4·1, 3·1, 2·1, 1·1
5 │ 5 │ 5·5, 5·4, 4·4, 5·3, 4·3, 5·2, 3·3, 4·2, 3·2, 5·1, 2·2/4·1, 3·1, 2·1, 1·1
  ┊   ┊

A brute force approach would be similar to selection sort, albeit without saving any of the values. A naïve 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 a·a. 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 2·2 .

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

The subproblem is still left unsolved:

How to find all products (in descending order of value) c·d, such that a·a > c·d > (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.

[Nominal Animal]

In grid form

You may be onto something there. If you think of an integer grid (or Cartesian coordinates),

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 a·b, (a-1)·b, (a-2)·b, down to b·b, 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?

[anduril462]

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

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.

[Nominal Animal]

Well, the following triple loop seems to work, but I don't think it is the best we could do...

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

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.

[Mario F.]

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.

[anduril462]

Just out of curiosity, why descending order, and why no duplicates? What is this for? Do you have any particular application(s) in mind?

[Mario F.]

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.

[megafiddle]

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

-

[anduril462]

This is the best I could come up with:
In pseudo 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

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

$ 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.

[Mario F.]

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.