fork(8) download
copy 
  1. #include <cmath>
  2. #include <iostream>
  3.  
  4. const double pheta = 0.5*(std::sqrt(5)+1);
  5.  
  6. double fib(unsigned int n)
  7. {
  8.     return (std::pow(pheta, n) - std::pow(1 - pheta, n)) / std::sqrt(5);
  9. }
  10.  
  11. unsigned int fibo_lowerbound(double N, unsigned min=0, unsigned max=1000)
  12. {
  13.     unsigned newpivot = (min+max)/2;
  14.     if (min==newpivot)
  15.         return newpivot;
  16.  
  17.     if (fib(newpivot) <= N)
  18.         return fibo_lowerbound(N, newpivot, max);
  19.     else
  20.         return fibo_lowerbound(N, min, newpivot);
  21. }
  22.  
  23. std::pair<double, double> fibo_range(unsigned int n)
  24. {
  25.     unsigned int lbound = fibo_lowerbound(n);
  26.     return std::make_pair(fib(lbound), fib(lbound+1));
  27. }
  28.  
  29. void display(unsigned int n)
  30. {
  31.     std::pair<double, double> range = fibo_range(n);
  32.     std::cout << "Fibonacci range wrapping " << n << " is "
  33.               << "[" << (unsigned long long) range.first << ", " << (unsigned long long) range.second << "]"
  34.               << std::endl;
  35. }
  36.  
  37. int main()
  38. {
  39.     display(1044);
  40.     display(8999913);
  41.     display(7);
  42.     display(67);
  43. }
  44.  
Success #stdin #stdout 0s 2724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Fibonacci range wrapping 1044 is [987, 1597]
Fibonacci range wrapping 8999913 is [5702887, 9227465]
Fibonacci range wrapping 7 is [5, 8]
Fibonacci range wrapping 67 is [55, 89]
https://ideone.com/H6SAd
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!