An interesting visualization demonstrating why not to use floating point calculations to determine if large integers are perfect squares

Floating Point Square Test

I've been working through The Art and Craft of Problem Solving, and there's been a few problems in it based on Pascal's Triangle. After some hours of scribbling numbers on paper, I got lazy and wrote up a generator for it in Python. The book wants the reader to examine some of the properties of the triangle, so I had my triangle renderer (renderer? ha, it's text!) take a function that'd return a boolean to determine if something should be shown or not. While scribbling odd and even values of the triangle on paper, I noticed that it kind of resembled Sierpinski's triangle, so I started with that.

Now this looked pretty neat to me, so I was thinking of another easy pattern I could look for. Perfect squares came to mind; just check to see if the square root of a number is an integer and you're all setup, right? I tried passing that function into the triangle renderer and beheld an interesting result.

It appeared as if perfect squares formed a kind of parabola past 100 rows of the triangle! What a discovery! Of course, I'm really doubting my naive perfect square test at this point, so I googled up a better one and tried that out. A less interesting result awaited me:

Even though I hadn't made the amazing discovery that perfect squares existed, buried within Pascal's triangle in an almost perfect parabola, I had learned to distrust floating point tests on gigantic integers. So there's that.

Code Follows:

import math

def pascal_generator():
    last = []
    while True:
        next = [last[i]+last[i-1] if 0 < i < len(last)
                else 1 for i in range(len(last)+1)]
        yield next
        last = next

def pascal_string(size, shade_function=lambda x:True):
    result = "\n"
    p = pascal_generator()

    for i in range(size):
        row =
        strrow = " ".join(["#" if shade_function(x)
                           else " " for x in row ])
        result +=  "%s #%d = %d\n" % (
            sum([1 for x in row
                 if shade_function(x)]))

    return result
def is_odd(x):
    return x % 2 == 1

def is_fsquare(x):
    return int(math.sqrt(x)) == math.sqrt(x)

def is_isquare(apositiveint):

    x = apositiveint // 2

    seen = set([x])
    while x * x != apositiveint and x > 0:
        x = (x + (apositiveint // x)) // 2
        if x in seen: return False
    return True

if __name__ == "__main__":
    #print pascal_string(140, is_odd)
    #print pascal_string(140, is_fsquare)
    print pascal_string(140, is_isquare)

Leave a Reply

Your email address will not be published. Required fields are marked *