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.
node script.js
y te evitas varias limitaciones de los navegadores