Infinite loop or just heavy math?

Community Off Topic
1

I can’t tell if I have an infinite loop, or if it lags/crashes because of the large workload.
Any help is greatly appreciated :slight_smile:

var mainnumber = 600851475143;

var factors = [];

for( var x = 0; x < 600851475143 + 1; x++){
    if(600851475143 % x === 0){
      factors.push(x);
  }
};
2

Its not infinite loop because for loop is final, although integers in javaScript are limited to 2^32( or 4294967296) by default . So yeah it crashes

2 Likes
3

I thought it was closed, but I don’t actually have much experience with infinite loops.

Thanks :slight_smile:

1 Like
4

You are welcome :grin:
PS: I strongly suggest you not to play with infinite loops nor mention them on interview for a job because causing them is considered to be fatal flaw in knowledge of programmer :slight_smile:

1 Like
5

Makes sense, thanks.

Is there a workaround for working with large numbers?

1 Like
6

Well in ES6 Number.MAX_SAFE_INTEGER is (2^53)-1 and that is 9007199254740991
However like i said earlier its “capped” on 2^32, i mean its not actually restricted to that point but you won’t use numbers higher that 2^32 in practice but if you have powerful pc you can play with 2^53 but remember the lesson with RAM consuming when playing with loops :stuck_out_tongue:

2 Likes
7

Signed 32 bit integers have a max value of 2^31-1, but since javascript numbers aren’t that, that isn’t a cap at all.
There’s not much memory usage in that loop, and unless the loop does nothing but fill up memory then that issue is dwarfed by how much time it takes.
An easy test to determine whether the loop is infinite is to make the number smaller.
Another test would be to just print out the progress

1 Like
8

Hmm strange, a cousin of mine told me that if you use loops with extremely high numbers in loop you will fill your memory in no-time, and that java script has a limit of doing infinite loops and will stop the browser eventually.And I think I’m pretty sure he mentioned that JS used to have cap in browser for loops. He is 40 year old professional programmer owning a company, and I think I am gonna trust him this one, and I agree that he could test this loop with console.log or document.write but wouldn’t it fill the memory like it was infinity loop? I know its not infinity but 600 billions is quite a number for a processing :wink:

9

Most modern javascript implementations use reference counting, objects get freed as soon as they drop to 0 references. Cyclic references get taken care of eventually by a second algorithm that looks for reachable objects and frees those that aren’t.
A loop variable might also only use the same 64 bits and never increase in memory usage.
A browser with an infinite or long-running loop will stop being responsive immediately, it’s busy running the loop.
If you create and discard lots of objects in your loop, then that too gets taken care of by reference counting. If you create objects that refer to each other so that reference counts don’t reach 0, then every now and then execution will halt while garbage collection runs, and then the loop can continue again.

If used to refers to 10 years back then it’s only that, used to, historical. Bitwise operators are done with 32 bit signed integers. but that’s something else.

And the memory thing is testable. Run the loop and watch memory.
Expected outcome: a) no growth b) grows but goes back down as garbage collection runs
Not expected: grows until memory is full

In nodejs it was glued at 6.1 MiB for a while, then jumped to 7.1 MiB and stayed there. A browser would be doing a whole lot of other stuff, but it wouldn’t be filling up your memory.

2 Likes
10

Don’t use large numbers. :wink:

11

Well, you could run the for loop from 0 to sqrt(6008514575143), calculated beforehand, to save time.

Instead of 600851475143 % x you could see what, say, 2^31 % x is, and then you could see what 600851475143/2^31 is. Call it y. Call the remainder of 6008514575143 z. Then you’d be able to test if (y * (2^31 % x) + z) % x is 0.

Also in this example you could do factors.push(x) and then put that in an array then do division at the end.

If you wanted to really test your programming skills, you could find a way to render super long integers as strings and then send two strings to a function and see what one divided by another is.

for instance div(123456789, 3) called to pseudocode below would be a good try. I can’t be precise, because I don’t think in JavaScript, but the basic thing to remember is: if we really want to, we can fake strings as numbers, though it’s probably not worth it.

function div(a,b) { # a and b are strings
 returnString = "";
for (y=1; y < 10; y++) { mult[y] = (b * y).to_string();
while (a > 0)
{
  for (y=9; y >= 0; y++)
  {
    if (mult[y] <= a) ## string comparison, not number
    {
      returnString = returnString + y.toString();
      # for character B in a/y; subtract ord(y) from ord(a) (reverse ascii value) and put it in an array. Then go through the string again, this time backwards. If ord(character B+1) is < 0, then subtract 1 from character B and add 10 to ord(character B+1). Chop off any trailing zeroes and add the appropriate number of zeroes to your final number.
      last y; ## end the loop
    }
  }
}
}

I hope this makes sense? I can clarify if you need.

1 Like
12

This makes perfect sense!

Thank you :slight_smile:

13

@andrewschultzchicago hit upon one not so obvious constraint: the square root. We need not iterate past that point. One of the fundamentals of factoring is finding the Prime factors. All numbers, except Primes, are multiples of one or more prime.

2 ^ 3 * 3 ^ 2 * 5 ^ 3

  8   *   9   *  125 

 =>     9000

9000 / 2 
4500 / 2
2250 / 2   => 2 ^ 3
1125 / 3
 375 / 3   => 3 ^ 2
 125 / 5
  25 / 5
   5 / 5   => 5 ^ 3
     1

8 iterations is all it would take to factor the primes in 9000. We can quickly deduce all non-prime factors from this simple list. Multiply any of the above primes together.