View Single Post
Old 2013-09-24, 05:53   #1
William Edwards
 
Sep 2013

1 Posts
Default searching part of the space using binary search

(I'm a rank hobbyist and I doubt my input is especially inspired, and I really just want to find out how useful the pattern I noticed is. Apologies aside:)

I was looking at the part of the hyperbolic curve near the middle where the curve is very nearly diagonal, and noticed a simple, exploitable pattern:

http://media.tumblr.com/2ecc00039204...acK1r3qp3f.png

(You'll see that I chose to plot y going downwards, like a times-table.)

Near the centre of the curve those squares go diagonally for some long run and then take one step downwards. This is because the curve is slightly greater than 45o, obviously.

And if (x+1)*(y-1) < target, then x*y must also be less than target. You are only interested in finding and evaluating where it goes down one.

So you can travel those diagonals using a binary search or by division.

Here is my blog post about this: http://williamedwardscoder.tumblr.co...g-big-integers

I'm curious as to if others have already noticed this, or exploited this?
William Edwards is offline   Reply With Quote