Logic Problem with BigInteger Method

Joined
Nov 29, 2019
Messages
2
Reaction score
0
This is the description of the problem I am working on:

public static void hittingIntegerPowers(int a, int b, int t, int[] out)
Define two positive integers to be “close enough for government work” if their absolute difference multiplied by the given tolerance level t is at most equal to the smaller of those two numbers. For example, the integers 2000 and 2007 are “close enough” when t = 100, since the difference 7 multiplied by 100 gives 700, which is less than 2000. On the other hand, the integers 2000 and 2050 would not be close enough for t = 100, although they would be close enough for a wider tolerance of t = 10. Tolerance of t = 100 corresponds to the notion of being within one percent, but without using any division or floating point numbers to compute this. The more narrow tolerance of t = 100000 would require these powers to be within one thousandth of a percent of each other, which ought to satisfy even the most ardent six sigma advocate auditing this course from the business school. Given two positive integers a and b and the desired tolerance t, this method should find and return find the smallest integer powers pa and pb so that when a is raised to the power of pa, and b is raised to the power of pb, the resulting two numbers are close enough for government work. Since these powers can get pretty big, as you can see in the table below, you need to perform these calculations using the BigInteger type. However, this is only for the actual powers that might end up having tens of thousands of digits; the exponents pa and pb are guaranteed to fit inside the int type for all the test cases given to your method.

This is the solution I have come up with so far:
Java:
public static void hittingIntegerPowers(int a, int b, int t, int[] out) {
            BigInteger bigA = BigInteger.valueOf(a);
            BigInteger bigB = BigInteger.valueOf(b);
            
            BigInteger currentPowerA = bigA;
            BigInteger currentPowerB = bigB;
            BigInteger tolerance = BigInteger.valueOf(t);

            int pa = 1;
            int pb = 1;
            
            while (pa < 1000) {
                while (pb <= pa){
                    BigInteger diff = currentPowerA.subtract(currentPowerB).abs();
                    if (diff.multiply(tolerance).compareTo(bigA.min(bigB)) <= 0) {
                        out[0] = pa;
                        out[1] = pb;
                        return;
                    }
                    pb++;
                    currentPowerB = currentPowerB.multiply(bigB);
                }
                pa++;
                currentPowerA = currentPowerA.multiply(bigA);
                pb = 1;
                currentPowerB = bigB;
            }
        }

There has to be some sort of logical problem in the while loop because using inputs a = 2, b = 3 and t = 100, the array out stays at [0,0]. The code seems to work fine with examples where the final pa and pb are different in value by one (a = 2, b = 4, t = 100).

I appreciate any help with the logic of the program or other approaches to solve the problem.
 
Joined
Sep 21, 2022
Messages
121
Reaction score
15
Code:
if (diff.multiply(tolerance).compareTo(bigA.min(bigB)) <= 0)

The comparison should use currentPowerA and currentPowerB, not bigA and bigB.
 
Joined
Sep 21, 2022
Messages
121
Reaction score
15
I think you can remove your inner loop.
Code:
pa=1
pb=1
LOOP
  IF currentPowerB too small
    pb++
  ELSE
    IF currentPowerB too large
      pa++
    ELSE
      solution found
      exit loop

too small means:
currentPowerB*(t+1) < currentPowerA*t

too large means:
currentPowerA*(t+1) < currentPowerB*t
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,755
Messages
2,569,537
Members
45,022
Latest member
MaybelleMa

Latest Threads

Top