# simulate a 32-bit signed integer overflow in a recurrence function

Considering the following recurring equation: which is this factorial function: I want to find the value of x where f(x) = 0.

Actually, the solution is impossible with Mathematica, and it's pretty normal. But, in some computer languages which have explicit typing and type casting, this could cause an Integer overflow if we were using 32-bit signed integer such as:

2147483647 + 1 = -2147483648

-2147483648 - 1 = 2147483647

With Mathematica, it is possible to simulate a 32-bit signed integer and the integer overflow behavior by: By example, in Mathematica, -2147483648 * 42 = -901943132160. But, on a computer using 32-bit signed integer, -2147483648 * 42 = 0. So, y32[-2147483648 * 42)] = 0.

Without the 32-bit signed integer simulation, the recurring function would be:

a[n_] = a[n] /. RSolve[{a[n + 1] == (n + 1)*a[n], a == 10}, a[n], n][]


My y32() function is:

y32[x_] := BitAnd[x, BitShiftLeft[1, 32] - 1] -
BitShiftLeft[
BitAnd[BitShiftRight[BitAnd[x, BitShiftLeft[1, 32] - 1], 31], 1],
32]


But as ybeltukov said in comment, it could just be:

Mod[x, 2^31, -2^31]


I tried:

a[n_] = a[n] /.
RSolve[{a[n + 1] == y32[(n + 1)*a[n]], a == 10}, a[n], n][]


But it did not work.

How can I use my y32() function in my recurrence function?

FindRoot[a[n] == 0, {n, ??}] should output 42.

• Mave you considered using Mod? – kirma Nov 7 '14 at 5:59
• I am not sure a simple Modulo coud convert a number in 32-bit signed integer.. – Pier-Alexandre Bouchard Nov 7 '14 at 6:00
• I haven't applied this to your problem, but wouldn't Mod[x + 2^31, 2^32] - 2^31 convert an overflown two's complement signed 32-bit integer "back" to the range - with wraparound? – kirma Nov 7 '14 at 6:31
• @kirma There is third argument in Mod: Mod[x, 2^31, -2^31] – ybeltukov Nov 7 '14 at 10:07
• Answer is 42 (some people say the answer to everything is 42...) – Daniel Lichtblau Nov 7 '14 at 21:14