The Fibonacci Sequence and the Perfect Square

00_my_recapitulation.md

####My search for the perfect solution to find a number in the Fibonacci sequence in Ruby My name is Daniela Grossmann and started learning Ruby in July this year when I got accepted for the Fall Cohort at Dev Bootcamp. As preparation we got a few exercises with RSpec running in the background to control our solutions. One week ago, out of curiosity, I tried to create exercises by writing my own RSpec tests and made all of them available for other students after consulting with Jesse Farmer, my future teacher. One of my exercises was to write a program which takes a number and checks if it's one of the Fibonacci sequence. I also wrote a solution for this problem which was the following, but Jesse told me, there is a better one.

def is_fibonacci?(i)
   arr = [0,1]
   until arr.last >= i
      a,b = arr.pop(2)
      arr.push(a,b,a+b)
   end
   if arr.last == i
      true
   else
      false
   end
end

I took the bait and worked on it until today - more or less intense (but I dreamed about it, as they predicted, that this could happen, when I applied). Jesse led my through the problem, motivated and calmed me, when I needed it. I learned a lot, like the use of Benchmark, lots of Math, one or two things about me and how much I will love starting Dev Bootcamp in October. Now I'm going to tell you about the path from my first solution to find that one:

require 'Abst'
def is_fibonacci?(n)
  perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? Abst.isqrt(n)**2 == n : false
end

RESIDUES = {
   256 => [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]
}

My first step on this path was the insight, that I can use the fact, that a number n is a Fibonacci number when 5n^2+4 or 5n^2-4 is a perfect square. Not that much of a problem so far, but using Math.sqrt(n) even with #to_i doesn't provide the precise results for large numbers that I would need to solve this. So the following solution was fast for small numbers, but the output for larger numbers was wrong.

def is_fibonacci?(n)
   perfect_square?(5n^2+4) || perfect_square?(5n^2-4)
end

def perfect_square?(n)
   Math.sqrt(n).round**2 == n
end

So my next quess was to find a better way to calculate a root. Therefore the Newton's Method was handy and I added the following code which made the program very slow and me very disappointed.

# ...
def perfect_square?(n)
   isqrt(n)**2 == n
end

def isqrt(n)
   a = newton(1,n)
   b = newton(a,n)
   until b >= a-1
      a = b
      b = newton(a,n)
   end
   b
end

def newton(x,n)
   (x+(n/x))/2
end

Then I learned about quadratic residue and how to reduce the amount of potential perfect squares by evaluating m % 4 == 1 and m % 4 == 0 - since only numbers meeting these two conditions can be perfect squares.

# ...
def perfect_square?(n)
   n%4 == 1 || n%4 == 0 ? isqrt(n)**2 == n : false
end
# ...

I experimented with more numbers and number combinations, but this one made it significantly faster again.

# ...
def perfect_square?(n)
   if not [0,1].include?(n%4)
      return false
   elsif not [0,1,4].include?(n%5)
      return false
   elsif not [0,1,2,4].include?(n%7)
      return false
   elsif not [0,1,4,7].include?(n%9)
      return false
   elsif not [0,1,3,4,9,10,12].include?(n%13)
      return false
   elsif not [0,1,2,4,8,9,13,15,16].include?(n%17)
      return false
   end
   isqrt(n)**2 == n
end
# ...

I experimented with binary operators to get rid of the moduli by using n & (x-1) instead of n % x but it only works for a number 'x = 2^y` and the real next step was to pre-calculate the quadratic residues using code, because I calculated it for modulo 256.

def is_fibonacci?(n)
   perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? isqrt(n)**2 == n : false
end

def isqrt(n)
   a = newton(1,n)
   b = newton(a,n)
   until b >= a-1
      a = b
      b = newton(a,n)
   end
   b
end

def newton(x,n)
   (x+(n/x))/2
end

RESIDUES = {
   256 => [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]
}

I was back on track and the program was again faster. Now I took a closer look at my isqrt(n) method. I learned that using a number closer to the solution as an initial number, it will get faster. I tried a few things like using again Math.sqrt(n).to_i which was fast but not precise enough, then I used the discrete logarithm, which is about finding the number e that has 2^e <= n < 2^(e+1) and replace 1 in the initial newton() method with 2^[(e+2)/2] and then I tried Math.log2(n).to_i which has the same issues as Math.sqrt(n).to_i.

# ...
def isqrt(n)
#  a = newton(1,n)
#  a = newton(Math.sqrt(n).to_i,n)
#  a = newton(get_initial(n),n)
   a = newton(Math.log2(n).to_i,n)
   b = newton(a,n)
   until b >= a-1
      a = b
      b = newton(a,n)
   end
   b
end

def get_initial(n)
   e = 1
   until n >= 2**e && n < 2**(e+1)
      e += 1
   end
   2**((e+2)/2)
end
# ...

Finally I found the Gem Abst and it's additions to the Math methods. It has methods like Abst.isqrt(n), Abst.ilog2(n) and #square?(). I experimented with all of them but the fastest result was this one:

require 'Abst'
# ...
def perfect_square?(n)
   RESIDUES[256][n % 256] ? Abst.isqrt(n)**2 == n : false 
end
# ...

By the way: the resulting program was ten times faster than my first one and more than hundred times faster than some in between. It was great going through this exercise and getting a taste of how amazing the time at Dev Bootcamp will be. Thanks Jesse for this experience.

2012-09-08_fibonacci.md

After I accidentally deleted my original protocol, I'm trying to recreate it. I excepted the challenge Jesse gave me to build a better solution, after I wrote the the exercise about the fibonacci sequence.

My original solution was:

def is_fibonacci?(i)
   arr = [0,1]
   until arr.last >= i
      a,b = arr.pop(2)
      arr.push(a,b,a+b)
   end
   if arr.last == i
      true
   else
      false
   end
end

The better solution for it seems to be using the fact that a fibonacci number n is a perfect square in one of that cases: 5n^2+4 or 5n^2-4 and I learned about the Newton's Method and how I can create with it an Integer Square Root.

def perfect_square?(n)
   isqrt(n)**2 == n
end

def isqrt(n)
   a = test(1,n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

def test(x,n)
   (x+(n/x))/2
end

def is_fibonacci_fancy?(n)
   perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

But this was not that easy to find, because in my first experiments I had to find out, that you get wired results when you use Math.sqrt(n) with a really big number, because the result is a Float:

1.9.3p194 :001 > x = 12345678990123456788889**2
  => 152415789727175735869534827062942783113854321 
1.9.3p194 :002 > Math.sqrt(x)
  => 12345678990123456000000.0 
1.9.3p194 :003 > Math.sqrt(x).to_i
  => 12345678990123456266240 
1.9.3p194 :004 > Math.sqrt(x).round
  => 12345678990123456266240 

2012-09-09_fibonacci.md

Jesse showed me how to use Benchmark to test the speed of a programm. At this point my whole program looked like this:

require 'benchmark'

# first solution
def is_fibonacci?(i)
   arr = [0,1]
   until arr.last >= i
      a,b = arr.pop(2)
      arr.push(a,b,a+b)
   end
   if arr.last == i
      true
   else
      false
   end
end

# second solution
def perfect_square?(n)
   isqrt(n)**2 == n
end

def isqrt(n)
   a = test(1,n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

def test(x,n)
   (x+(n/x))/2
end

def is_fibonacci_fancy?(n)
   perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

puts ""
puts "Benchmarking fibonacci test"
puts ""

ITERATIONS = 1000

BIG_FIB = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Benchmark.bm(label_width = 20) do |x|
   x.report('is_fibonacci?') do
      ITERATIONS.times { is_fibonacci?(BIG_FIB) }
   end

   x.report('is_fibonacci_fancy?') do
      ITERATIONS.times { is_fibonacci_fancy?(BIG_FIB) }
   end
end

I found out, is that my first solution was way faster, and I was confused. Shouldn't be this be faster? Why the effort then?

                            user     system      total        real
 is_fibonacci?          0.730000   0.010000   0.740000 (  0.824680)
 is_fibonacci_fancy?    2.350000   0.030000   2.380000 (  3.384336)

Jesse showed me his results and a glimpse on how fast it can get with the right changes. And I was hooked again.

                           user     system      total        real
 is_fibonacci?          0.160000   0.010000   0.170000 (  0.171053)
 is_fibonacci_fancy?    6.710000   0.130000   6.840000 (  6.855523)
 is_fibonacci_jesse?    0.020000   0.000000   0.020000 (  0.019890)

The next tip Jesse gave me, was that I can eliminate some of the non-perfect squares with the fact that n % 4 has to be 1 or 0 when it's a perfect square and showed me how to test the speed of the calculation of the perfect squares by using Benchmark again.

require 'Benchmark'

# ...
# second solution
def perfect_square?(n)
   isqrt(n)**2 == n
end

# ...
# third solution
def perfect_square2?(n)
   n%4 == 1 || n%4 == 0 ? isqrt(n)**2 == n : false
end

def is_fibonacci_faster?(n)
   perfect_square2?(5*n**2 + 4) || perfect_square2?(5*n**2 - 4)
end

# ...

MAX = 2**62

SIZE = ARGV.fetch(0) { 1000000 }.to_i

SAMPLE = Array.new(SIZE) { rand(MAX) }

puts ""
puts "Benchmarking #{SIZE} random integers for perfect square test..."
puts ""

Benchmark.bm(label_width = 20) do |x|
   x.report('perfect_square?') do
      SAMPLE.each { |i| perfect_square? i }
   end

   x.report('perfect_square2?') do
      SAMPLE.each { |i| perfect_square2? i }
   end
end

The Output:

                            user     system      total        real
 is_fibonacci?          0.730000   0.010000   0.740000 (  0.824680)
 is_fibonacci_fancy?    2.350000   0.030000   2.380000 (  3.384336)
 is_fibonacci_faster?   2.360000   0.030000   2.390000 (  3.584306)

                            user     system      total        real
 perfect_square?       11.560000   0.100000  11.660000 ( 15.451392)
 perfect_square2?       6.130000   0.050000   6.180000 (  8.712449)

So it didn't seam that it mattered much for the fibonacci solution, but with this I halved the time for the perfect_squares?(n) method. The mathematical term for it is quadratic residue. When I looked it up I found this article about quadratic residue and tried different solutions, like this one:

# ...

def perfect_square3?(n)
   if not [0,1].include?(n%4)
      return false
   elsif not [0,1,4].include?(n%5)
      return false
   elsif not [0,1,2,4].include?(n%7)
      return false
   elsif not [0,1,4,7].include?(n%9)
      return false
   elsif not [0,1,3,4,9,10,12].include?(n%13)
      return false
   elsif not [0,1,2,4,8,9,13,15,16].include?(n%17)
      return false
   end
   isqrt(n)**2 == n
end

# ...

The Output:

                            user     system      total        real
 perfect_square?       11.560000   0.100000  11.660000 ( 15.451392)
 perfect_square2?       6.130000   0.050000   6.180000 (  8.712449)
 perfect_square3?       3.260000   0.050000   3.310000 (  5.502269)

and I was able to half the time again.

To calculate the numbers I wrote this program:

def q_residue(n)
   arr = (1..200).to_a
   arr.map! {|a| a**2}
   mod_arr = []
   arr.each do |a|
      b = a%n
      if not mod_arr.include?(b)
         mod_arr << b
      end
   end
puts "number of different quadratic residue of modulo #{n} is #{mod_arr.length}"
puts "#{mod_arr.sort}"
end

q_residue(4)
q_residue(5)
q_residue(7)
q_residue(9)
q_residue(13)
q_residue(17)
q_residue(256)

2012-09-11_fibonacci.md

I tried to increase speed with binary operators: x%y == x&(y-1) But I found out, that it's not working for every number, because y hat to be 2^i that it works. And it got much slower...

# ...
def perfect_square4?(n)
   if not [0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57, 64, 65, 68, 73, 81, 89, 97, 100, 105, 113, 121, 129, 132, 137, 144, 145, 153, 161, 164, 169, 177, 185, 193, 196, 201, 209, 217, 225, 228, 233, 241, 249].include?(n&255)
      return false
   end
   isqrt(n)**2 == n
end
# ...

The Output:

                            user     system      total        real
 perfect_square?       11.560000   0.100000  11.660000 ( 15.451392)
 perfect_square2?       6.130000   0.050000   6.180000 (  8.712449)
 perfect_square3?       3.260000   0.050000   3.310000 (  5.502269)
 perfect_square4?       8.490000   0.170000   8.660000 (  9.534292)

The next tip from Jesse was this code piece:

# We can add other moduli whose quadratic residues we wish to check
RESIDUES = {
   11 => [true, true, false, true, true, true, false, false, false, true, false]
}

def is_residue_mod_11?(q)
   return RESIDUES[11][q % 11]
end

and I made this out of it:

def perfect_square6?(n)
   check_quadratic_residues(n) == true ? isqrt(n)**2 == n : false
end

def check_quadratic_residues(n)
   is_residue_mod_4?(n) ||
   is_residue_mod_5?(n) ||
   is_residue_mod_7?(n) ||
   is_residue_mod_9?(n) ||
   is_residue_mod_13?(n) ||
   is_residue_mod_17?(n)
end

RESIDUES = {
   4 => [true, true, false, false],
   5 => [true, true, false, false, true],
   7 => [true, true, true, false, true, false, false],
   9 => [true, true, false, false, true, false, false, true, false],
   13 => [true, true, false, true, true, false, false, false, false, true, true, false, true],
   17 => [true, true, true, false, true, false, false, false, true, true, false, false, false, true, false, true, true]
}
def is_residue_mod_17?(n)
   return RESIDUES[17][n % 17]
end

def is_residue_mod_13?(n)
   return RESIDUES[13][n % 13]
end

def is_residue_mod_9?(n)
   return RESIDUES[9][n % 9]
end

def is_residue_mod_7?(n)
   return RESIDUES[7][n % 7]
end

def is_residue_mod_5?(n)
   return RESIDUES[5][n % 5]
end

def is_residue_mod_4?(n)
   return RESIDUES[4][n % 4]
end

The speed was down again:

 perfect_square6?      12.240000   0.090000  12.330000 ( 15.030139)

So Jesse gave me this partial code to find out, which quadratic residue is the fastest:

MAX    = 2**256
SAMPLE = Array.new(100) { rand(MAX) }

RESIDUES = {
   # pre-generate a hash for residues from 1 to 100
}

def perfect_square?(n, mod)
   return false unless RESIDUES[mod][n % mod]
   return isqrt(n)**2 == n
end

Benchmark.bm(label_width=15) do |x|
   (4..100).each do |mod|
      x.report("mod #{mod}")
         SAMPLE.each { |n| perfect_square?(n, mod) }
      end
   end
end

Because I had to fill the hash with quadratic residues, I coded:

def fill_residues_hash
   (1..100).each do |i|
      RESIDUES[i] = find_residues(i)
   end
end

def find_residues(i)
   arr = (1..200).to_a
   arr.map! {|a| a**2}
   mod_arr = []
   arr.each do |a|
      b = a%i
      if not mod_arr.include?(b)
         mod_arr << b
      end
   end
   mod_arr
end

fill_residues_hash

This are some of the results:

 ...
 mod 90            0.010000   0.000000   0.010000 (  0.017206)
 mod 91            0.020000   0.000000   0.020000 (  0.034593)
 mod 92            0.020000   0.000000   0.020000 (  0.020609)
 mod 93            0.030000   0.000000   0.030000 (  0.034094)
 mod 94            0.040000   0.000000   0.040000 (  0.043057)
 mod 95            0.020000   0.000000   0.020000 (  0.042695)
 mod 96            0.010000   0.000000   0.010000 (  0.007263)
 mod 97            0.040000   0.000000   0.040000 (  0.058718)
 ...

2012-09-12_fibonacci.md

I changed the speed test from yesterday a little bit, so that I get the precalculated arrays of the quadratic residues I needed.

def find_residues(i)
   arr = (1..300).to_a
   arr.map! {|a| a**2}
   mod_arr = []
   mod_arr2 = []
   arr.each do |a|
      b = a%i
      if not mod_arr.include?(b)
         mod_arr << b
      end
   end
   precheck_residue(mod_arr.sort,i)
end

def precheck_residue(mod_arr,i)
   pre_arr = []
   i.times do |a|
      mod_arr.include?(a) ? pre_arr << true : pre_arr << false
   end
   pre_arr
end

puts "#{find_residues(256)}"

fill_residues_hash

Then I made a new method for the perfect_square?(n)

# ...
def is_fibonacci?(n)
   perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? isqrt(n)**2 == n : false
end

def isqrt(n)
   a = test(1,n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

def test(x,n)
   (x+(n/x))/2
end

RESIDUES = {
   256 => [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]
}
# ...

And the speed is again better:

                            user     system      total        real
 perfect_square?       2.310000   0.010000   2.320000 (  2.630173)
# the fastest result before was:
 perfect_square3?       3.260000   0.050000   3.310000 (  5.502269)

2012-09-14_fibonacci.md

Today Jesse gave me the next hint for the solution: I should read the chapter of the book A Course in Computational Algebraic Number Theory by Henry Cohen beginning at page 28. I had a hard time reading it, because on one hand I didn't see all the pages in the preview of Amazon, and on the other hand, reading a Mathematical book and in a foreign language can be tough. But I found a hint in a passage, which said, that its faster when you use a initial number closer to the perfect square number, so I changed the 1 to a Math.sqrt(n).to_i first.

# ...
def isqrt(n)
#  a = test(1,n)
   a = test(Math.sqrt(n).to_i,n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

#...

The speed was not bad:

  user     system      total        real
 perfect_square?        0.970000   0.000000   0.970000 (  0.991583)

But Jesse objected that the point of all this was to get rid of Math.sqrt(), because it suffers from precision errors. And he told me to find the discrete logarithm, which is about finding the number e that has 2^e <= n < 2^(e+1) and replace 1 in the initial test with 2^[(e+2)/2]

# ...
def isqrt(n)
#  a = test(1,n)
#  a = test(Math.sqrt(n).to_i,n)
   a = test(get_initial(n),n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

def test(x,n)
   (x+(n/x))/2
end

def get_initial(n)
   e = 1
   until n >= 2**e && n < 2**(e+1)
      e += 1
   end
   2**((e+2)/2)
end
#...

But I was back to slow:

                            user     system      total        real
 perfect_square?        6.870000   0.030000   6.900000 (  7.390690)

Jesse told me to get a taste of the possible speed, I should use Math.log2(n).to_i, but again with the hint that it has the same precision problems as Math.sqrt(n).to_i. I used it with this result:

                           user     system      total        real
perfect_square?        2.550000   0.010000   2.560000 (  2.753708)
~~~  

Now I'm searching for an own method to find ilog2(n).

2012-09-15_fibonacci.md

Today I found a gem Abst which can be a possible solution, because it has the ilog2(n) method defined. First I had to install this gem: ~~ macair1:misc dgrossmann$ gem install abst /Users/dgrossmann/.rvm/rubies/ruby-1.9.3-p194/bin/gem:4: warning: Insecure world writable dir /usr/local in PATH, mode 040777 Fetching: abst-0.2.0.gem (100%) Successfully installed abst-0.2.0 1 gem installed Installing ri documentation for abst-0.2.0... Installing RDoc documentation for abst-0.2.0... ~~

And that's how my whole code looked like at this point.

require 'benchmark'
require 'Abst'

def is_fibonacci?(n)
  perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? isqrt(n)**2 == n : false
end

def isqrt(n)
#  a = test(1,n)
#  a = test(Math.sqrt(n).to_i,n)
#  a = test(get_initial(n),n)
#  a = test(Math.log2(n).to_i,n)
   a = test(Abst.ilog2(n),n)
   b = test(a,n)
   until b >= a-1
      a = b
      b = test(a,n)
   end
   b
end

def test(x,n)
   (x+(n/x))/2
end

# def get_initial(n)
#    e = 1
#    until n >= 2**e && n < 2**(e+1)
#       e += 1
#    end
#    2**((e+2)/2)
# end

RESIDUES = {
   256 => [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]
}

# Testing perfect square
# ======================
puts "true: #{perfect_square?(1234567823456789234567**2)}"
puts "false: #{perfect_square?(1234567823456789234567**2-4)}"

# Testing the speed
# =================
puts ""
puts "Benchmarking fibonacci test"
puts ""

ITERATIONS = 1000

BIG_FIB = 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125

Benchmark.bm(label_width = 20) do |x|
  x.report('is_fibonacci?') do
    ITERATIONS.times { is_fibonacci?(BIG_FIB) }
  end
end

MAX = 2**62

SIZE = ARGV.fetch(0) { 1000000 }.to_i

SAMPLE = Array.new(SIZE) { rand(MAX) }

puts ""
puts "Benchmarking #{SIZE} random integers for perfect square test..."
puts ""

Benchmark.bm(label_width = 20) do |x|
  x.report('perfect_square?') do
    SAMPLE.each { |i| perfect_square? i }
  end
end

Output:

true: true
false: false

Benchmarking fibonacci test

                           user     system      total        real
is_fibonacci?          2.770000   0.010000   2.780000 (  2.820434)

Benchmarking 1000000 random integers for perfect square test...

                           user     system      total        real
perfect_square?        2.740000   0.010000   2.750000 (  2.806307)

Just for comparison - the first was the speed with 1 as the initial number, the second the one with Math.sqrt(n):

 perfect_square?       2.310000   0.010000   2.320000 (  2.630173)
 perfect_square?        0.970000   0.000000   0.970000 (  0.991583)

But taking a closer look at the 'Abst Gem', I found a Abst.isqrt(n) and a Abst.fibonacci(n) method.

# ...
def is_fibonacci?(n)
  perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? Abst.isqrt(n)**2 == n : false 
end
# ...

With this little change I was able to get rid of all the other methods and got this result:

Benchmarking fibonacci test

                           user     system      total        real
is_fibonacci?          0.080000   0.000000   0.080000 (  0.102757)

Benchmarking 1000000 random integers for perfect square test...

                           user     system      total        real
perfect_square?        1.810000   0.000000   1.810000 (  1.841121)

The Abst.fibonacci(n) is not useful for this case, because it shows the number in the fibonacci sequence with the index number n.

1.9.3-p194 :002 > require "Abst"
 => true 
1.9.3-p194 :003 > Abst.fibonacci(13)
 => 233 

And I found even more when I looked through the documentation: Abst adds more methods to other Classes, like the Integer Class. There is a method called #square? which reduces the code to this:

require 'Abst'

def is_fibonacci?(n)
   (5*n**2 + 4).square?() || (5*n**2 - 4).square?() ? true : false
end

I needed here the true and false statement, because I get a number as a result when it's true.

The speed is not that bad, but the program with the ilog2(n) method has a faster result:

                           user     system      total        real
is_fibonacci?          0.100000   0.000000   0.100000 (  0.102633)

# with ilog2(n):
is_fibonacci?          0.080000   0.000000   0.080000 (  0.086109)
# my first solution:
is_fibonacci?          0.730000   0.010000   0.740000 (  0.824680)

Then I did one last test:

equire 'benchmark'
require 'Abst'

# USING Abst.isqrt(n)
def is_fibonacci?(n)
  perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square?(n)
   RESIDUES[256][n % 256] ? Abst.isqrt(n)**2 == n : false
end

RESIDUES = {
   256 => [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]
}

# USING n.square?()
def is_fibonacci_1?(n)
   (5*n**2 + 4).square?() || (5*n**2 - 4).square?() ? true : false
end

# USING Absi.log2(n)
def is_fibonacci_2?(n)
  perfect_square?(5*n**2 + 4) || perfect_square?(5*n**2 - 4)
end

def perfect_square_2?(n)
   RESIDUES[256][n % 256] ? Abst.ilog2(n)**2 == n : false
end

# ...

Benchmarking fibonacci test

                           user     system      total        real
is_fibonacci?          0.080000   0.000000   0.080000 (  0.086749)
is_fibonacci_1?        0.090000   0.000000   0.090000 (  0.100021)
is_fibonacci_2?        0.080000   0.000000   0.080000 (  0.092596)

Benchmarking 1000000 random integers for perfect square test...

                           user     system      total        real
perfect_square?        1.850000   0.010000   1.860000 (  2.066206)
perfect_square_2?      1.210000   0.010000   1.220000 (  1.293141)