Bifalgorithm post · Computer science one · Recursion

How can BigInteger be used for large recursive Fibonacci values?

How can BigInteger be used for large recursive Fibonacci values? (Computer science one · Recursion) — "Java provides an arbitrary precision data type, BigInteg…

Ideas in this flowchart

  • BigInteger permite calcular valores enteros de Fibonacci arbitrariamente grandes.
  • BigInteger es un tipo de datos de precisión arbitraria.
  • Los números de Fibonacci crecen exponencialmente.
  • Con int solo se puede representar hasta F45.
  • BigInteger permite representar valores de Fibonacci mucho mayores.
  • El ejemplo implementa fibMem mediante recursión y memorización.
  • ¿Es n menor que cero?
  • Si n < 0, se lanza una IllegalArgumentException porque el valor no está definido.
  • ¿Es n menor o igual que uno?
  • Para n <= 1, la función devuelve BigInteger.ONE.
  • Para valores mayores, la función utiliza el caso recursivo con memorización.
  • ¿Existe ya un resultado almacenado para n?
  • Si no existe, se calculan recursivamente fibMem(n-1, m) y fibMem(n-2, m).
  • Los dos valores se suman y el resultado se guarda en el mapa.
  • Si existe, se devuelve directamente el resultado memorizado.
  • Después del cálculo y almacenamiento, se devuelve el resultado.
Feed/

How can BigInteger be used for large recursive Fibonacci values?

No cover

Channel

Computer science one

1 page

"Java provides an arbitrary precision data type, BigInteger that can be used to compute arbitrarily large integer values. Since Fibonacci numbers grow exponentially, using an int we could only represent up to to F 45. Using BigInteger we can support much larger values. An example:\n\n1 public static BigInteger fibMem(int n, Map<Integer, BigInteger> m) {\n\n2 if(n < 0) {\n\n3 throw new IllegalArgumentException(\"Undefined for n < 0\");\n\n4 } else if(n <= 1) {\n\n5 return BigInteger.ONE;\n\n6 } else {\n\n7 BigInteger result = m.get(n);\n\n8 if(result == null) {\n\n9 BigInteger a = fibMem(n-1, m);\n\n10 BigInteger b = fibMem(n-2, m);\n\n11 result = a.add(b);\n\n12 m.put(n, result);\n\n13 }\n\n14 return result;\n\n15 }\n\n16 }"

Flowchart preview
👍
0
0 comments0 shares

Sign in to view and post comments.