Skip to main content
Code Review

Return to Answer

remove style fragments
Source Link
Sam Ginrich
Sam Ginrich
  • 119
  • 2

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet's Formula" due to floating arithmetics takes O(n^1.25)emphasized textO(n^1.25) time
  3. rcgldr's algorithm with O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10, Logarithmic Large Scale Complexity of Fibonacci algorithmsenter image description here

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet's Formula" due to floating arithmetics takes O(n^1.25)emphasized text time
  3. rcgldr's algorithm with O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10, Logarithmic Large Scale Complexity of Fibonacci algorithms

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet's Formula" due to floating arithmetics takes O(n^1.25) time
  3. rcgldr's algorithm with O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10, enter image description here

Description of diagram axis added.
Source Link
Sam Ginrich
Sam Ginrich
  • 119
  • 2

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60)O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet"Binet's Formula" due to floating arithmetics takes O(n^1.25)emphasized text time
  3. rcgldr's algorithm with O(n^1.029)O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10, Logarithmic Large Scale Complexity of Fibonacci algorithms

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet Formula" due to floating arithmetics takes O(n^1.25) time
  3. rcgldr's algorithm with O(n^1.029) time.

Logarithmic Large Scale Complexity of Fibonacci algorithms

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet's Formula" due to floating arithmetics takes O(n^1.25)emphasized text time
  3. rcgldr's algorithm with O(n^1.029) time.

The diagram shows evaluation time for Fn in seconds over n, both axis logarithmic with base 10, Logarithmic Large Scale Complexity of Fibonacci algorithms

Source Link
Sam Ginrich
Sam Ginrich
  • 119
  • 2

Evaluating Asymptotic Complexity e.g. with gmp library, shows that rcgldr's algorithm, implementing efficient matrix powers with O(log(n)) mutlipications, has best performance among presented algorithms.

Below compared for n in range 0 .... 647028207

  1. Straight Iteration, n steps, takes O(n^1.60) time.
  2. "Golden Ratio", i.e. above called the "Binet Formula" due to floating arithmetics takes O(n^1.25) time
  3. rcgldr's algorithm with O(n^1.029) time.

Logarithmic Large Scale Complexity of Fibonacci algorithms