Path: csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups: comp.lang.javascript
Subject: Re: Primality sieve challenge
Date: Tue, 19 Jan 2016 16:54:23 +0000
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <87d1sx4iio.fsf@bsb.me.uk>
References: <5b608a56-e16b-4467-a0ce-4e30f6796920@googlegroups.com> <871t9gfa2z.fsf@bsb.me.uk> <8b01caa9-8c09-4e69-915b-81b67eba7edc@googlegroups.com> <0b16c016-5128-4b68-8046-fbec55700ec3@googlegroups.com> <60329a65-27f8-483e-bd6e-e262e952ee6f@googlegroups.com> <871t9fd6p7.fsf@bsb.me.uk> <XnsA5937CEFD5E87eejj99@194.109.6.166> <ih9q9b9hn97rstn00pcq8mgttf84ftgk71@4ax.com> <XnsA593C548780B7eejj99@194.109.6.166> <gukq9bdam69pinh9q10djlq43vv8mv3a55@4ax.com> <57bd7c90-81fd-4fe9-b329-1d58db4ff3f1@googlegroups.com> <dfc4d40c-d9ef-4dab-a0b4-16d0f55776a1@googlegroups.com> <n7k49m$54l$1@news.albasani.net> <3b97a09c-9d25-4c00-a831-f8f6acc28567@googlegroups.com> <4df099db-79b7-4b8f-b608-9e964d790e67@googlegroups.com> <a62d7a3c-8525-4139-9548-d6161c34529c@googlegroups.com> <0e769fb3-75b6-4f86-905a-d71c4934d63f@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="8201"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/CtO1amEgu7PCBUDRFa176AmvKTE4+EJc="
Cancel-Lock: sha1:+0WHbLiLB0wf8suSv5pB/S5eTl8= sha1:1JAF0Mwu6eQmDZRPo0YweWfABPw=
X-BSB-Auth: 1.cbf3d775af6f57a65062.20160119165423GMT.87d1sx4iio.fsf@bsb.me.uk
Xref: csiph.com comp.lang.javascript:29351

jonas.thornvall@gmail.com writes:

> Den tisdag 19 januari 2016 kl. 16:15:55 UTC+1 skrev jonas.t...@gmail.com:
>> Den tisdag 19 januari 2016 kl. 15:23:26 UTC+1 skrev Michael Haufe (TNO):
>> > On Tuesday, January 19, 2016 at 1:35:01 AM UTC-6, jonas.t...@gmail.com wrote:
>> >  
>> > > Well 5532 pages but i did generate fibonacci which of courcse
>> > > alot easier taking up 87 pages took 3 minutes. Now i do realise
>> > > there is a huge difference.
>> > > 
>> > > But if i really can do the math in quasilinear time i should be able to do it.
>> > > First i must find out how fast i really can multiply.
>> > 
>> > fib(n) can be determined in O(n)/O(n) space/time [1]
>> > 
>> > [1]
>> > <https://thenewobjective.com/blog/2013/01/dynamic-programming-for-great-justice/#bonus>
>> 
>> I will use the plain fibonacci counter but instead adding previous i
>> will multiply and see how "far digitplaces" fast it go. I have some
>> ideas "forgotten" that i will try to enhance it with.
>
> If i just can get the base to be of anysize, i am sure i will be able
> to multiply in near linear time.

"near"?  What is your algorithm?

> Start was 2*1 and base 10000000 i managed to go upto 29 th took 106429
> ms it was 174369 digits long, to long to post.

Now you have thread here and in sci.math with the same content.  As I
said there, that's a big slow, but it may be all you can get with a
simple multiplication algorithm written in JavaScript.

<snip>
-- 
Ben.