mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
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
Old 2013-09-24, 09:42   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 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
Old 2013-09-24, 11:45   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Per your blog post, you can certainly prove a number to be prime, without factoring it, but the algorithms for doing that are pretty complex. The search term is 'primality proving'.

It is much easier to think about factorization in algebraic terms, and much easier to find patterns using algebaic relationships than to try to spot colors in a table. For example, your experiments appear to be a graphical rediscovery of Fermat's factorization algorithm, which works especially well when factors are near the square root of the input. Fermat's algorithm is very easy to express algebraically (it's hundreds of years old).

The objective with factorization is always to factor something bigger, and doing it by eye will not scale. At this point you if you want to really accelerate things you should go to wikipedia and read up on integer factorization; the articles on the various methods are quite good there and you'll be amazed how quickly they work.

You also need to get into the habit of doing background reading before coding, especially if you are a professional programmer, because in 2013 it's very difficult to think of something new in the computer field and very easy to leverage the work of others.

Last fiddled with by jasonp on 2013-09-24 at 11:46
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Riesel Primes k*2^n-1, k<300 [Part II] Kosmaj Riesel Prime Search 1021 2021-02-25 10:42
I'm sure this is an ID-10-T error on my part petrw1 PrimeNet 1 2017-09-25 23:12
Numbers in Tables : Part 2 wustvn Puzzles 9 2007-12-31 05:14
best Fermat search space program wanted jasong Programming 0 2007-10-03 20:34
Circles part 2 mfgoode Puzzles 10 2004-12-27 15:17

All times are UTC. The time now is 05:32.

Fri Mar 5 05:32:48 UTC 2021 up 92 days, 1:44, 0 users, load averages: 1.85, 1.77, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.