View Single Post
Old 2013-09-24, 09:42   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by William Edwards View Post
(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?
Complete nonsense.
R.D. Silverman is offline   Reply With Quote