Sunday, March 8, 2020

Problem-solving in programming #2 - Factoring a REALLY large number

Triangle Of Penrose, Optical Illusion, Impossible

Continuing with our discussion about using algorithms to factor numbers, let's try and use that Java algorithm to factor the number 1385012925728371650682372927611246185812:

First problem: the variable used to take the number value is of the primitive int type, which can only hold up until a maximum value of (2^31)-1 = 2147483647. The next primitive value then is double, which also won't help us: the biggest value it takes is (2^63)-1 = 18446744073709551615.

Our number sits between 2^130 and 1^131, so we need extra tools to do so. An intuitive approach would be to just use the BigInteger library and adapt the previous algorithm, right?

Let's go ahead and try that:

I went and added into the main a few lines to have a general idea of how long the computer would take to calculate that. Oh, bear in mind that I am using an Intel I7-8700K @ 3.70 GHz with 16 GB RAM, 6 cores of sheer willpower and brute force. It should work, right?

Well, it's been a few minutes now and...still no factorization.

Perhaps it is best if we try a different approach. Creativity sometimes call for some additional strategies. It often requires us to think before we act. Let's try and understand a little bit more about the problem we are trying to solve here, to see if we can do something to improve the efficiency of our code above.

First, let's take a look at our process there. Going back to our example from the last post, the number 426. It is even, so 2 is a factor.

426/2 = 213

We start looking for the divider + 1 (since odd numbers aren't divisible by two) according to our algorithm above, right? Then 3:

213/3 = 71

And now, we start checking numbers, one by one. Four is our next, but why would we check divisibility by four if we already know the number is divisible by two? Actually, why would we check for divisibility for any multiple of 2 after this point?

So, one approach would be to change the code like this:

This way, we first factor it by two as much as we can, and then we proceed with the even numbers. At this point, we have to stop and think: is there anything else I can do to improve my code?

At this point, I will stop and say you need to put your brain to work and try to come up with your own improvements to this code. Feel free to reach out to me by email: I am looking forward to seeing your ideas!

Later this week I will come back to this problem to discuss additional improvements and some practical implications of this problem :D

Just a sneak peek preview: in the problem after this one I'll discuss the concept of recursion.
Author Image

About Ricardo Prins
Ricardo Prins is a Software Engineer who thinks that technology is not the answer to all our problems.

No comments:

Post a Comment