Reputation: 319

How Do I Optimize This Algorithm To Handle Large Integers?

I have two integers x and y.

Rule:

If x > y : x = x - y and y = 2 * y;
If y > x : y = y - x and x = 2 * x;
If y == x : not infinite loop

The question is, will the two integers be an infinite loop or not?

Here is my code:

private static boolean IsPairLoop(int first, int second)
{
    boolean loop = false;
    HashMap<Integer, Integer> round_record = new HashMap<>();
    int[] first_round = new int[]{first, second};

    while ((first_round[0] != -1 && first_round[1] != -1))
    {
        if (round_record.containsKey(first_round[0]))
        {
            loop = true;
            break;
        }
        round_record.put(first_round[0], first_round[1]);
        PlayRound(first_round);
    }
    return loop;
}

private static void PlayRound(int[] round)
{
    if (round[0] > round[1])
    {

       round[0] -= round[1];
       round[1] += round[1];

    }
    else if (round[0] < round[1])
    {

       round[1] -= round[0];
       round[0] += round[0];

    }
    else
    {
        round[0]  = -1;
        round[1]  = -1;
    }
}

This works fine for small integers. However, this is painfully slow when the integer difference is really large. Integer range is 1 to 2^30 for both x and y. What can I do to make this fast even when the integers difference is large?

Upvotes: 1

Answers (3)

user1196549

Reputation:

In this problem, the sum x + y is invariant, and if it is odd, x == y is impossible.

Then if x and y have the same parity, after one iteration they become both even and remain so, and the problem is unchanged if you divide both by 2.

Hence the "instantaneous" solution:

while (x + y) & 1 == 0:
    if x == y:
        print "Not infinite"
        break
    if x > y:
        x= (x - y) / 2
    else:
        y= (y - x) / 2
else:
    print "Infinite"

As one of the arguments loses at least one bit on every iteration, there are never more than 64 iterations for 32 bits integers (and in practice much less, most of the time 0 !).

A variant is possible and can make sense for bignumbers:

if x == y, conclude finite.
if x and y have a different number of trailing zeroes, conclude infinite.
otherwise, discard the trailing zeroes and perform the reduction according to x > y or y > x and loop.

Upvotes: 3

Ry-

Reputation: 224983

Let’s work backwards a bit. What can produce x == y? The difference between the previous x and y has to be equal to twice the smaller of the two, i.e. the larger has to be three times the smaller. Things that don’t loop infinitely so far:

{n, n}
{n, 3n}

Where can {n, 3n} come from? Either

n is a difference a − b for some a > b, and 3n = 2b
3(a − b) = 2b
3a − 3b = 2b
3a = 5b
a = 5/3 b

A pair {m, 5/3 m} is something that produces {n, 3n} on the next step. (m has to be divisible by 3, but that’s okay.)
3n is a difference a − b for some a > b, and n = 2b
(a − b)/3 = 2b
a − b = 6b
a = 7b

A pair {m, 7m} is the only other thing that can produce {n, 3n} on the next step.

An updated list:

{n, n}
{n, 3n}
{n, 7n}
{n, 5/3 n}

Seems like a good time to generalize those last steps.

{n, qn} happens when:

n is a difference a − b for some a > b, and qn = 2b
q(a − b) = 2b
qa − qb = 2b
qa = (2 + q)b
a = (2 + q)/q b
or qn is a difference a − b for some a > b, and n = 2b
(a − b)/q = 2b
a − b = 2qb
a = (2q + 1)b

So if q = m/n is in the list, these are also in the list:

(2n + m)/m
(2m + n)/n

q = 1 generates:

(2 + 1)/1 = 3
2×1 + 1 = 3

q = 3 generates:

3
(2 + 3)/3 = 5/3
2×3 + 1 = 7

q = 5/3 generates:

3
5/3
7
(2 + 5/3)/(5/3) = (6 + 5)/5 = 11/5
(2×5/3) + 1 = 10/3 + 1 = 13/3

q = 7 generates:

3
5/3
7
11/5
13/3
(2 + 7)/7 = 9/7
2×7 + 1 = 15

Hmm… that’s pretty interesting. Let’s sort the list by the numerator:

3/1
5/3
7/1
9/7
11/5
13/3
15/1

Based on that pattern, I’d expect 17/15 to come next. Generating a list sorted by denominator with a computer:

Looks an awful lot like m/n where n is odd, m > n, and m + n is a power of two. So one way to optimize your algorithm would be:

private static boolean isPairLoop(int first, int second)
{
    if (first == second) return false;
    if (first > second) return isPairLoop(second, first);
    if (first == 0) return true;

    int d = gcd(first, second);
    return Integer.bitCount(first / d + second / d) != 1;
}

private static int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

Takes quadratic time on the number of digits on bigints.

Now you just have to prove that it works. ^{_{I hope it works.}}

Upvotes: 1

Paul Hankin

Reputation: 58280

Instead of using a hashmap, use Floyd's cycle detection algorithm. Not only will this avoid large memory use, it will also avoid costly boxing and unboxing between int and Integer.

A second optimisation is to re-write the recurrence relations via a change of variables:

s = x+y
t = x-y

Then the recurrence relations become:

if t=0, stop
if t>0, s'=s, t'=2t-s
if t<0, s'=s, t'=2t+s

Note in this formulation, only the t variable changes.

The code (untested) will look something like this:

private static int step(int s, int t) {
    if (t>0) return 2*t - s;
    if (t<0) return 2*t + s;
    return 0;
}

private static boolean IsPairLoop(int first, int second) {
    int s = first+second;
    int t_slow = first-second;
    int t_fast = t_slow;
    while(t_slow != t_fast) {
        t_slow = step(s, t_slow);
        t_fast = step(s, step(s, s_fast));
    }
    return t_slow != 0;
}

You may need to replace int with long if first+second can overflow.

I think, given the preconditions, you never get a t that goes off to infinity (since it's always true that |t| < s). But you may wish to double-check, perhaps adding some sort of assertion into your code.

Upvotes: 1

How Do I Optimize This Algorithm To Handle Large Integers?

Answers (3)

Related Questions