Path: csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!nntpspool01.opticnetworks.net!aioe.org!.POSTED!not-for-mail
From: bartekltg <bartek@gmail.com>
Newsgroups: comp.programming
Subject: Re: really? (lame question about primes)
Date: Wed, 02 Sep 2015 16:27:23 +0200
Organization: Aioe.org NNTP Server
Lines: 61
Message-ID: <ms710a$beb$1@speranza.aioe.org>
References: <5e5de47a-7353-4ffc-9f5d-ec083d1d63ba@googlegroups.com> <kt4Fx.394338$3n4.170027@fx35.am4> <44a165dc-8447-4ae0-8695-557a7ddf00cf@googlegroups.com> <ms3peh$o5v$1@dont-email.me> <_RfFx.418341$bt.398932@fx32.am4> <ms5iql$65b$1@speranza.aioe.org> <VpsFx.514615$vz7.459274@fx07.am4> <ms6f8u$umv$1@speranza.aioe.org> <lwzFx.371089$0B6.10953@fx27.am4> <ms6ov4$evq$1@dont-email.me> <yPBFx.319631$IK6.308401@fx46.am4> <ms6rm0$td4$1@speranza.aioe.org> <ms6uia$57r$1@dont-email.me>
NNTP-Posting-Host: 8yDXz2POMePMu60eIS0/Vw.user.speranza.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@aioe.org
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.8.0
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.programming:5721

On 02.09.2015 15:47, David Brown wrote:
> On 02/09/15 14:56, bartekltg wrote:
>> On 02.09.2015 14:19, Richard Heathfield wrote:
>>> On 02/09/2015 13:12, David Brown wrote:
>>>>
>>> <snip>
>>>>
>>>> There are a number of ways of doing this check faster than the
>>>> bit-for-bit long division you suggested elsewhere,
>>>
>>> The advantage of that way is that it's easy to explain, and relatively
>>> easy to implement. Having said that, I *haven't* implemented it (in
>>> software). My bignum library uses Algorithm D, from TAOCP II.
>>
>> I think explain something by using wrong algorithm can hurt
>> someone who think, so propably everyone who is listening to
>> 'how to factorize an integer;-)'
>>
>> But we can resurect this idea.
>>
>> Table of all n-digits prime can be too big for the universe,
>> so we have to generate it. One ot the simplest method is
>> to implement 'nextprime' - function that get the next odd*)
>> number and run fast primality test (Miller-Rabin),
>> repeat it until the number is pseudoprime.
>>
>
> The principle here is that to find the factors of C, we run through all
> primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
> are other faster algorithms, but I don't know of any.)  If you know for
> sure the number of digits in A, then you could start 10^(noOfDigits-1),
> but that would only save 10% of the test time.
>
> Testing for the primality of each A is going to take a great deal more
> time than simply trying C % A == 0, even with a probable prime test.  It
> is simply not worth doing.
>
> What would be worth doing, I think, is to keep a track of A % p for p in
> the first n primes.  As you run through the A's, adding 2 to A each
> step, you add 2 to each of these remainders in your tracking array.  If
> these hit 0 (modulo their prime), then A is clearly non-prime and you
> can skip it.  This will let you skip a number of your test divisions
> with relatively little work - as you make that array of n primes bigger,
> you cut out yet more divisions.  However, there is going to be a point
> where doing this tracking for the modulo A % p will cost more (in memory
> or speed) than 1/p times the cost of calculating C % A - and when you
> reach that, you don't want to track any more modulos.
>
> I suspect there is scope for some interesting data structures to hold
> this list of modulos, rather than a simple array - perhaps a priority
> queue in a Fibonacci heap?


Yes, this is the "standard" algorithm I was talking about, in the last
post I even mentioned the heuristic you described it the third
paragraph.
Are you sure you wanted to post it as the answer to my post?

bartekltg