1
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.

7
  • para números de esa magnitud javascript tal vez no sea la mejor elección ver es.stackoverflow.com/questions/197/…. tal vez tengas que convertirlos a un string para cachearlos, igualmente habrá algun límite Commented el 24 ago. 2018 a las 1:42
  • si no entiendo mal el limite práctico almacenando strings sería 2^27 dígitos stackoverflow.com/a/28841863/1423096 con un límite teórico de 2^53 dígitos en ES7 Commented el 24 ago. 2018 a las 2:05
  • Gracias por los datos, estoy viendo el post ... si quieren entender mejor el problema dejo el link de el codeabbey.com/index/task_view/fibonacci-sequence
    – Mooenz
    Commented el 24 ago. 2018 a las 2:08
  • vale, para este tipo de stress tests en javascript tal vez te convenga instalarte node (motor v8 js), llamas al script onda node script.js y te evitas varias limitaciones de los navegadores Commented el 24 ago. 2018 a las 2:10
  • 1
    @aloMalbarez lo tengo a un 99%, ahora solo necesito solucionar el hecho de que js deja a todo numero mayor a los 15 dígitos en notacion euler, creo que recortare el numero y dejarlo con solo los primero 15 dígitos, pero es toda una hazaña.
    – Mooenz
    Commented el 24 ago. 2018 a las 2:18

2 respuestas 2

1

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.


8
  • Soy sincero, no entendí lo que trataste de hacer xd de todas formas muchas gracias por responder. de paso te digo que el problema radica en el numero generado por la funcion fibo. ejemplo: fibo(263) == 4114000911454431885883343305337966369078499341559272017, esto dara false :/
    – Mooenz
    Commented el 31 ago. 2018 a las 21:38
  • 1
    =P te agrego una explicación en el proceso Commented el 31 ago. 2018 a las 22:11
  • hahaha dale, pero si entendiste mi problema?
    – Mooenz
    Commented el 31 ago. 2018 a las 22:16
  • 1
    creo que sí: usando una librería para números grandes, la segunda y tercer versión sacan fibo(10000) y fibo(85000) de una (no tengo enlace para el 85000) , el número resultante tiene 17764 dígitos Commented el 31 ago. 2018 a las 22:43
  • 1
    es por eso que propongo usar la libreria bigint es para números realmente grandes, fibo(85000) tiene 17764 digitos, fibo(263) tiene 55. si usas la representación interna de javascript llega un punto que torna infinito o la diferencia de redondeo del exponente hace que falle, el que haya ido hasta 85000 era para probar la librería pero se me queda sin memoria el javascript Commented el 1 sept. 2018 a las 0:16
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));

5
  • La situación es cuando uso un numero como el siguiente (4114000911454431885883343305337966369078499341559272017 ), el que poste al inicio igualmente sirve, gracias por el aporte.
    – Mooenz
    Commented el 24 ago. 2018 a las 1:42
  • pero que quieres lograr y otro no se te traba el navegador? Commented el 24 ago. 2018 a las 1:53
  • a eso quiero llegar, el navegador queda pegado por el while, y es por que el numero es tan grande que js lo reduce a la notación de euler. quiero lograr encontrar el indice de un numero fibonacci con mas de 200 digitos.
    – Mooenz
    Commented el 24 ago. 2018 a las 2:03
  • No el navegador no puede con tanto y por lo que se en javascript no reconoce la notación de euler aun que te lo muestra, ademas el while no sale prueba lo, con números pequeños para que veas. Commented el 24 ago. 2018 a las 2:47
  • Gracias por responder. El problema radica en el numero generado por la funcion fibo. ejemplo: fibo(263) == 4114000911454431885883343305337966369078499341559272017, esto dara false :/
    – Mooenz
    Commented el 31 ago. 2018 a las 22:02

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.