Numbers overflow problem

1

Hello.

I tried myself at implementing Fibnacci with memoization. This is my code:

let rec fib = (n, ~memo=Js.Dict.empty(), ()) => {
  let key = Js.Int.toString(n)
  Js.log(memo)
  switch Js.Dict.get(memo, key) {
  | Some(res) => res
  | _ =>
    switch n {
    | 1 | 2 => 1
    | _ =>
      let newRes = fib(n - 1, ~memo, ()) + fib(n - 2, ~memo, ())
      Js.Dict.set(memo, key, newRes)
      newRes
    }
  }
}
Js.log(fib(50, ()))

it seems to work, but from #47 the results seem to be wrong:

  '46': 1836311903,  // correct
  '47': -1323752223, // incorrect
  '48': 512559680,   // incorrect
  '49': -811192543,  // incorrect
  '50': -298632863   // incorrect

Running similar code in vanilla JavaScript gives correct results.

Why is this happening?

Thank you.

1 Like
2

I believe you have reached the max value for an int.

I.e.

Js.log(Js.Int.max)
// Prints 2147483647

I believe switching to floats should give you the equivalent behaviour as vanilla JavaScript:

let rec fib = (n: float, ~memo=Js.Dict.empty(), ()) => {
  let key = Js.Float.toString(n)
  Js.log(memo)
  switch Js.Dict.get(memo, key) {
  | Some(res) => res
  | _ =>
    switch n {
    | 1.0 | 2.0 => 1.0
    | _ => {
        let newRes = fib(n -. 1.0, ~memo, ()) +. fib(n -. 2.0, ~memo, ())
        Js.Dict.set(memo, key, newRes)
        newRes
      }
    }
  }
}

Js.log(fib(50.0, ()))
4 Likes
3

To further explain what’s happening, the maximum integer in ReScript is a 32 bit integer, whereas the JavaScript number type is 64 bits. ReScript enforces the 32 bit limit by appending a | 0 after every integer (In JS, all bitwise operators like | are 32 bit, so this automatically converts it).

In regular JS code, you probably aren’t adding | 0 to enforce the 32 bit limit, which is why the overflow isn’t happening. As @kevanstannard mentioned, using floats instead is the easiest way around the limit.

3 Likes
4

Can I ask why ReScript put the maximum size of a int to 32bits?

5

The reason they use 32-bit integers is that ReScript inherits the type system of OCaml. In OCaml, the standard int type is 32 bits. There is also a float type, which resembles the number type in JavaScript, along with an int64 type, which is 64 bits, but very different from float.

The bottom line is that ReScript isn’t changing the core type system or semantics of OCaml, which it is based on. They have made several patches to make things easier for JS interop (like uncurried function types), but most things remain the same.

4 Likes