Mismos datos no coinciden, Js (numero mayor a los 15 dígitos en notación E)

Question

let cont = 0;
let cache = [0,1,1];


function fibo(num) {
    if(!cache[num])
        cache[num] = fibo(num - 1) + fibo(num - 2)
        return cache[num]
}

function sequence(num) {
    do {
      cont++;
      fibo(cont)
      //console.log("En el Do")
    } while( !( cache.includes(num) ) ) 
    return cont;
}

El código anterior sirve (según mi criterio) para saber el indice de un numero fibonacci. Es decir, la función fibo(num) se ejecuta las veces necesarias hasta que el resultado coincida con numero fibonacci otorgado.

Pero tengo un problema con números extremadamente largos como: 4114000911454431885883343305337966369078499341559272017, el problema es que el numero guardado en el array (cache) es 4.114000911454431e+54 y el numero a buscar (numero fibonacci) es 4.114000911454432e+54.

No se si soy claro? si quieren ejecutar el código se inicia desde sequence.

Answer 1

Este codigo funciona pruebalo:

let cont = 0;
    let cache = [0,1,1];
    let res = 0;


    function fibo(num) {
      if(!cache[num])
        cache[num] = fibo(num - 1) + fibo(num - 2);
        console.log(cache);
        return cache[num]
     }

     function sequence(num) {
       while(res != num) {
        cont++;
        res = fibo(cont);
       }
       return cont+1;
      }

      console.log(sequence(1597));

Answer 2

Resumen:

• En el primer caso intenté lo que surgió de los comentarios, usar claves de texto en vez de números para el cache, se evitan los errores de precisión pero en algún momento crece demasiado el número para la representación interna de javascript y devuelve "infinito".

• Debido a esto me dije: ¿por qué no crear una representación numérica para números en base decimal de muchos dígitos?, necesitaría una base de mas de 10 para la representación interna e implementar las operaciones básicas + y -. Revivir el sistema sexagesimal (base 60) usando números, letras y algunos símbolos venía bien pero se me complicó el tema operaciones.

• Para el segundo intento entonces en vez de reinventar la rueda busqué una librería que maneje números grandes (BigInt). Con esta librería fue posible sacar el resultado de fibo(10000) pero aparecieron problemas de stack debido a que son muchas iteraciones recursivas (cada vez que abre una rama se guarda la info en el stack, cada vez que retorna se saca del stack).

• Tercer intento: combinación de "divide y vencerás" y "calentar el cache", al número se llega de a poco y escalonadamente, manteniendo el cache para siguientes iteraciones. El resultado: calcula fibo(85000) de una y sin transpirar, pero ir un poco mas lejos ya agota la memoria disponible.

---

1) claves de cache como strings

jajaja... infinity?

https://www.numberempire.com/fibonaccinumbers.php?number=1752

let cont = 0;
let cache = {
  "0": "0",
  "1": "1",
  "2": "1",
  "1752": "626412933222017131750251106239038184404619901191496173429666587960297214781918187729015583187558935933308644574983016355858116612560690415751645485244328002505519643294746218176604788108245189876572443197149250131401360563186035584737624471084969488892773152736832455171117033423571518755482917609868374896533911403957469365557602126327674376133576706157430249006624"
};

function fibo(num) {
  nst = num.toString()
  if (!cache[nst])
    cache[nst] = (fibo(num - 1) + fibo(num - 2)).toString();
  return cache[num]*1
}

console.log(fibo(1752))

---

2) claves de cache usando BigInt

Segundo Intento con librería bigInt -> https://github.com/peterolson/BigInteger.js

let cache = [];
cache[bigInt.zero] = bigInt.zero;
cache[bigInt.one] = bigInt.one;
cache[bigInt(2)] = bigInt.one;
/*
  "1752": "626412933222017131750251106239038184404619901191496173429666587960297214781918187729015583187558935933308644574983016355858116612560690415751645485244328002505519643294746218176604788108245189876572443197149250131401360563186035584737624471084969488892773152736832455171117033423571518755482917609868374896533911403957469365557602126327674376133576706157430249006624"
*/

function fibo(num) {
  num = bigInt(num);
  if (!cache[num])
    cache[num] =
    fibo(
      num.minus(1)
    ).add(
      fibo(
        num.minus(2)
      )
    );
  return cache[num];
}

let muestraInfo = function() {
  document.getElementById('length').innerHTML =
    document.getElementById('resultado').innerHTML.length + " dígitos" +
    "<br>" + Object.keys(cache).length + " claves en cache";
}
document.getElementById('borra').onclick = function() {
  cache = [];
  cache[bigInt.zero] = bigInt.zero;
  cache[bigInt.one] = bigInt.one;
  cache[bigInt(2)] = bigInt.one;
  muestraInfo();
}

document.getElementById('dale').onclick = function() {
  let res = fibo(document.getElementById('numero').value);
  document.getElementById('resultado').innerHTML = res;
  muestraInfo();
}

muestraInfo();

#resultado,
#length {
  float: left;
  width: 40vw;
  overflow: auto;
  margin: 2px;
  padding: 2px;
  border: 1px dashed red
}

.wrap {
  white-space: pre-wrap;
  /* CSS3 */
  white-space: -moz-pre-wrap;
  /* Firefox */
  white-space: -pre-wrap;
  /* Opera <7 */
  white-space: -o-pre-wrap;
  /* Opera 7 */
  word-wrap: break-word;
  /* IE */
}

<script src="https://peterolson.github.io/BigInteger.js/BigInteger.min.js"></script>

<body>
  <div>
    <input type="text" id="numero" value="15000">
    <button id="dale">Go</button>
  </div>
  <div id="resultado" class="wrap"></div>
  <div id="length"></div><button id="borra">clear cache</button>

</body>

En esta segunda vuelta va mejor pero se agota el callstack cada 10000 iteraciones aproximadamente, lo cual significa que si vas aumentando el número de a 10000 (y así llenando el cache) podes ir subiendo el límite.

---

3) claves de cache usando BigInt, precalentar el cache yendo de a incrementos que eviten el stackoverflow

Tercer intento agregar la secuencia para ir cargando el cache de a poco

let itera = 0,
  cachehits = 0,
  cache = [];
cache[bigInt.zero] = bigInt.zero;
cache[bigInt.one] = bigInt.one;
cache[bigInt(2)] = bigInt.one;

function fibo(num) {
  itera++
  num = bigInt(num);
  if (!cache[num]) {
    cache[num] =
      fibo(
        num.minus(1)
      ).add(
        fibo(
          num.minus(2)
        )
      );
  } else {
    cachehits++
  }
  return cache[num];
}

let muestraInfo = function(idx, chx) {
  document.getElementById('length').innerHTML =
    document.getElementById('resultado').innerHTML.length +
    " dígitos en el resultado" +
    "<br>" + Object.keys(cache).length + " claves en cache" +
    "<br>" + idx + " iteraciones" +
    "<br>" + chx + " hits de cache";
}
document.getElementById('borra').onclick = function() {
  cachehits = 0, itera = 0, cache = [];
  cache[bigInt.zero] = bigInt.zero;
  cache[bigInt.one] = bigInt.one;
  cache[bigInt(2)] = bigInt.one;
  muestraInfo(itera, cachehits);
}

document.getElementById('dale').onclick = function() {
  cachehits = 0, itera = 0;
  let limite = document.getElementById('numero').value;
  let i = 0;
  let res = fibo(i);
  // primero de a 10000
  while (i < limite) {
    res = fibo(i);
    i += 10000;
  }
  // si nos pasamos
  i -= 9999;

  // luego de a 1000
  while (i < limite) {
    res = fibo(i);
    i += 1000;
  }
  // si nos pasamos
  i -= 999;
  // luego de a 100
  while (i < limite) {
    res = fibo(i);
    i += 100;
  }
  // si nos pasamos
  i -= 99;
  // luego de a 1
  while (i < limite) {
    res = fibo(i);
    i++;
  }
  // y uno mas
  res = fibo(i);

  document.getElementById('resultado').innerHTML = res;
  muestraInfo(itera, cachehits);
}

muestraInfo(itera, cachehits);
document.getElementById('numero').focus();

#resultado,
#length {
  float: left;
  width: 40vw;
  overflow: auto;
  margin: 2px;
  padding: 2px;
  border: 1px dashed red
}

#numero {
  width: 4em;
  border: 1px dashed #eee;
  text-align: center;
}

.wrap {
  white-space: pre-wrap;
  /* CSS3 */
  white-space: -moz-pre-wrap;
  /* Firefox */
  white-space: -pre-wrap;
  /* Opera <7 */
  white-space: -o-pre-wrap;
  /* Opera 7 */
  word-wrap: break-word;
  /* IE */
}

<script src="https://peterolson.github.io/BigInteger.js/BigInteger.min.js"></script>

<body>
  <div>
    <em>fibo</em>(<input type="text" id="numero" value="1752">) =
    <button id="dale">Calcular</button>
  </div>
  <div id="resultado" class="wrap"></div>
  <div id="length"></div><button id="borra">clear cache</button>

</body>

Sigue estando un poco mejor calcula fibo(85000) de entrada pero también vuelca, tal vez usar workers dividiendo las tareas o usando algún otro tipo de algoritmo.

---