Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #29280 > unrolled thread

Primality sieve challenge

Back to article view | Back to comp.lang.javascript

Contents

  Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 01:40 -0800
    Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 02:20 -0800
    Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-17 16:24 +0000
      Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:03 -0800
        Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:17 -0800
          Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:22 -0800
            Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 11:32 -0800
            Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-18 00:13 +0100
              Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:10 -0800
            Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 01:20 +0000
              Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 12:16 +0100
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 11:25 +0000
                  Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 12:43 +0100
                    Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:18 -0800
                    Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:25 -0800
                Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 09:52 -0800
                  Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 19:23 +0100
                    Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-18 10:48 -0800
                    Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 13:09 -0800
                      Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-18 13:14 -0800
                        Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 22:45 +0100
                        Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 14:23 -0800
                          Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 22:56 +0000
                            Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 15:02 -0800
                              Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 16:04 -0800
                          Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-19 02:42 +0100
                            Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 23:34 -0800
                              Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 01:34 -0800
                              Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-19 06:23 -0800
                                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 07:10 -0800
                                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 07:15 -0800
                                  Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 08:34 -0800
                                    Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-19 16:54 +0000
                                    Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-19 08:57 -0800
                                      Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 10:18 -0800
                                        Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 10:59 -0800
                              Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-20 01:33 +0100
                                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-20 02:10 -0800
                                  Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-20 02:21 -0800
                                    Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-20 10:45 +0000
                                    Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-20 06:43 -0800
                                    Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-20 15:21 -0800
                                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-21 03:18 +0100
                                  Re: Primality sieve challenge Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2016-01-21 12:12 +0000
                            Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-21 23:20 +0000
                              Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-22 19:44 +0100
                                Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-23 21:50 +0000
                                  Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-24 01:26 +0100
                                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-23 17:54 -0800
                                  Re: Primality sieve challenge "Chris M. Thomasson" <nospam@no-spam.ws> - 2016-01-24 13:34 -0800
                                    Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-25 00:21 +0000
                                      Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-25 03:08 +0100
                                        Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-24 19:35 -0800
                                  Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-25 03:53 -0800
                  Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 19:32 +0000
          Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-17 19:51 +0000
            Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 13:43 -0800
    Re: Primality sieve challenge "Chris M. Thomasson" <nospam@nospam.nospam> - 2016-01-17 12:46 -0800
      Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 09:50 -0800
        Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-18 20:09 +0100
          Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 19:28 +0000
            Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-18 21:37 +0100
              Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-18 13:12 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 13:46 -0800
                  Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 14:00 -0800
                Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 13:47 +0100
                  Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-19 14:04 +0000
                    Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 19:59 +0100
                  Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-19 10:55 -0800
                    Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 20:04 +0100
                      Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-19 13:42 -0800
                        Re: Primality sieve challenge Erwin Moller <erwinmollerusenet@xs4all.nl> - 2016-01-21 17:21 +0100
                          Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-03 19:52 +0100
          Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-19 19:43 +0000

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#29332

Scott Sauyet <scott.sauyet@gmail.com> wrote on 18 Jan 2016 in 
comp.lang.javascript:

> Gene Wirchenko wrote:
>> Evertjan wrote:
> 
>>> Please do not use your own definitions in a discussion.
>> 
>> Where did I use my own definition?  O(n) is using big-O notation.
>> 
>> See https://en.wikipedia.org/wiki/Big_O_notation for the explanation.
> 
> And note that this notation is very commonly used when discussing
> algorithms.  This is not at all an unusual notion of Gene's

Okay.


-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#29335

Den måndag 18 januari 2016 kl. 22:14:18 UTC+1 skrev Scott Sauyet:
> Gene Wirchenko wrote:
> > Evertjan wrote:
> 
> >> Please do not use your own definitions in a discussion.
> > 
> > Where did I use my own definition?  O(n) is using big-O notation.
> > 
> > See https://en.wikipedia.org/wiki/Big_O_notation for the explanation.
> 
> And note that this notation is very commonly used when discussing
> algorithms.  This is not at all an unusual notion of Gene's
> 
>   -- Scott

Do you guys knows if the biggest found prime it is binary or decimal digits?
From wiki "17,425,170 digits"
I think my program will be able to test it for primality, i would like an link to the ascii file. "if decimal". I prefer decimal before a binary.

It doesn't seem that big?

And if i can check that one for primality in desent time, i guess i will be able to find a bigger.

Largest known prime number
From Wikipedia, the free encyclopedia

As of January 2016, the largest known prime number is 257,885,161 - 1, a number with 17,425,170 digits. It was found in 2013 by the Great Internet Mersenne Prime Search (GIMPS).

[toc] | [prev] | [next] | [standalone]

#29336

jonas.thornvall@gmail.com writes:
<snip>
> Do you guys knows if the biggest found prime it is binary or decimal digits?
> From wiki "17,425,170 digits"

Decimal digits.

> I think my program will be able to test it for primality, i would like
> an link to the ascii file.

You can download it from http://www.mersenne.org/primes/

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29337

Den måndag 18 januari 2016 kl. 23:56:26 UTC+1 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
> <snip>
> > Do you guys knows if the biggest found prime it is binary or decimal digits?
> > From wiki "17,425,170 digits"
> 
> Decimal digits.
> 
> > I think my program will be able to test it for primality, i would like
> > an link to the ascii file.
> 
> You can download it from http://www.mersenne.org/primes/
> 
> <snip>
> -- 
> Ben.

Is it trivial or impressing i manage to test it for primality in Javascript?

[toc] | [prev] | [next] | [standalone]

#29339

Den tisdag 19 januari 2016 kl. 00:02:22 UTC+1 skrev jonas.t...@gmail.com:
> Den måndag 18 januari 2016 kl. 23:56:26 UTC+1 skrev Ben Bacarisse:
> > jonas.thornvall@gmail.com writes:
> > <snip>
> > > Do you guys knows if the biggest found prime it is binary or decimal digits?
> > > From wiki "17,425,170 digits"
> > 
> > Decimal digits.
> > 
> > > I think my program will be able to test it for primality, i would like
> > > an link to the ascii file.
> > 
> > You can download it from http://www.mersenne.org/primes/
> > 
> > <snip>
> > -- 
> > Ben.
> 
> Is it trivial or impressing i manage to test it for primality in Javascript?

I think i missed an if there, well let see how big numbers i can work with first. If i can beat all other webbased tests for primality i am satisfied.

So lets go for something in the range of the fibonacci i constructed 200 000 digits to start with.

[toc] | [prev] | [next] | [standalone]

#29341

On 01/18/2016 23:23, jonas.thornvall@gmail.com wrote:
> Do you guys knows if the biggest found prime it is binary or decimal digits?
> From wiki "17,425,170 digits"
> I think my program will be able to test it for primality, i would
> like an link to the ascii file. "if decimal". I prefer decimal before a binary.
> 
> It doesn't seem that big?
> 
> And if i can check that one for primality in desent time, i guess i
> will be able to find a bigger.
> 
> Largest known prime number
> From Wikipedia, the free encyclopedia
> 
> As of January 2016, the largest known prime number is 257,885,161 -
> 1, a number with 17,425,170 digits. It was found in 2013 by the Great
> Internet Mersenne Prime Search (GIMPS).

The number is 2 to the power of 57885161 - 1, not 257885161 - 1.
That tells you that the number has exactly 57885161 binary digits.
The 17425170 digits are therefore decimal.

> It doesn't seem that big?

A common estimate for the number of atoms in the observable universe is
10^80. That's a number with ~80 digits. You're going for a number with
17425170 digits. The raw decimal number takes ~17MB to store in an
uncompressed ASCII file, like you're proposing. If you were to print it
out, you'd need around 4k-5k sheets of paper (pages).

Or think about it in terms of time. The square root of that number is
around 10^8712585... let's call it an even 10^8700000 as your upper
boundary for trial division.
Your algorithm narrows the field by 90% (I haven't looked at it, just
taking your word for it). That means you only have to check 10^8699999
numbers, which is nice. Assuming you could test a trillion (10^12)
numbers per second (on average) and that you had started your program
shortly after the Big Bang, today you would have around 10^8699970
numbers left to test.

Big enough yet?

The number has been the record holder for 3 years now. Why do you think
that is? I don't mean to discourage your scripting efforts, but this
goal seems seriously out of reach with your approach. For a quick
comparison, today's statistics for the GIMPS project are

    Teams      864
    Users      143,562
    CPUs       1,195,522
    TFLOP/s    324.606
    GHz-Days   162,303

And that's with a specialized algorithm and software optimized to do
this one task. If you really are serious about finding prime numbers,
you'll have to acquire the mathematical knowledge and familiarize
yourself with existing algorithms (or just join GIMPS). And if you're
hell-bent on doing it in JavaScript, you will need to learn the basics
of the language first.


- stefan

[toc] | [prev] | [next] | [standalone]

#29342

Den tisdag 19 januari 2016 kl. 02:42:22 UTC+1 skrev Stefan Weiss:
> On 01/18/2016 23:23, jonas.thornvall@gmail.com wrote:
> > Do you guys knows if the biggest found prime it is binary or decimal digits?
> > From wiki "17,425,170 digits"
> > I think my program will be able to test it for primality, i would
> > like an link to the ascii file. "if decimal". I prefer decimal before a binary.
> > 
> > It doesn't seem that big?
> > 
> > And if i can check that one for primality in desent time, i guess i
> > will be able to find a bigger.
> > 
> > Largest known prime number
> > From Wikipedia, the free encyclopedia
> > 
> > As of January 2016, the largest known prime number is 257,885,161 -
> > 1, a number with 17,425,170 digits. It was found in 2013 by the Great
> > Internet Mersenne Prime Search (GIMPS).
> 
> The number is 2 to the power of 57885161 - 1, not 257885161 - 1.
> That tells you that the number has exactly 57885161 binary digits.
> The 17425170 digits are therefore decimal.
> 
> > It doesn't seem that big?
> 
> A common estimate for the number of atoms in the observable universe is
> 10^80. That's a number with ~80 digits. You're going for a number with
> 17425170 digits. The raw decimal number takes ~17MB to store in an
> uncompressed ASCII file, like you're proposing. If you were to print it
> out, you'd need around 4k-5k sheets of paper (pages).
> 
> Or think about it in terms of time. The square root of that number is
> around 10^8712585... let's call it an even 10^8700000 as your upper
> boundary for trial division.
> Your algorithm narrows the field by 90% (I haven't looked at it, just
> taking your word for it). That means you only have to check 10^8699999
> numbers, which is nice. Assuming you could test a trillion (10^12)
> numbers per second (on average) and that you had started your program
> shortly after the Big Bang, today you would have around 10^8699970
> numbers left to test.
> 
> Big enough yet?
> 
> The number has been the record holder for 3 years now. Why do you think
> that is? I don't mean to discourage your scripting efforts, but this
> goal seems seriously out of reach with your approach. For a quick
> comparison, today's statistics for the GIMPS project are
> 
>     Teams      864
>     Users      143,562
>     CPUs       1,195,522
>     TFLOP/s    324.606
>     GHz-Days   162,303
> 
> And that's with a specialized algorithm and software optimized to do
> this one task. If you really are serious about finding prime numbers,
> you'll have to acquire the mathematical knowledge and familiarize
> yourself with existing algorithms (or just join GIMPS). And if you're
> hell-bent on doing it in JavaScript, you will need to learn the basics
> of the language first.
> 
> 
> - stefan

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.

[toc] | [prev] | [next] | [standalone]

#29343

Den tisdag 19 januari 2016 kl. 08:35:01 UTC+1 skrev jonas.t...@gmail.com:
> Den tisdag 19 januari 2016 kl. 02:42:22 UTC+1 skrev Stefan Weiss:
> > On 01/18/2016 23:23, jonas.thornvall@gmail.com wrote:
> > > Do you guys knows if the biggest found prime it is binary or decimal digits?
> > > From wiki "17,425,170 digits"
> > > I think my program will be able to test it for primality, i would
> > > like an link to the ascii file. "if decimal". I prefer decimal before a binary.
> > > 
> > > It doesn't seem that big?
> > > 
> > > And if i can check that one for primality in desent time, i guess i
> > > will be able to find a bigger.
> > > 
> > > Largest known prime number
> > > From Wikipedia, the free encyclopedia
> > > 
> > > As of January 2016, the largest known prime number is 257,885,161 -
> > > 1, a number with 17,425,170 digits. It was found in 2013 by the Great
> > > Internet Mersenne Prime Search (GIMPS).
> > 
> > The number is 2 to the power of 57885161 - 1, not 257885161 - 1.
> > That tells you that the number has exactly 57885161 binary digits.
> > The 17425170 digits are therefore decimal.
> > 
> > > It doesn't seem that big?
> > 
> > A common estimate for the number of atoms in the observable universe is
> > 10^80. That's a number with ~80 digits. You're going for a number with
> > 17425170 digits. The raw decimal number takes ~17MB to store in an
> > uncompressed ASCII file, like you're proposing. If you were to print it
> > out, you'd need around 4k-5k sheets of paper (pages).
> > 
> > Or think about it in terms of time. The square root of that number is
> > around 10^8712585... let's call it an even 10^8700000 as your upper
> > boundary for trial division.
> > Your algorithm narrows the field by 90% (I haven't looked at it, just
> > taking your word for it). That means you only have to check 10^8699999
> > numbers, which is nice. Assuming you could test a trillion (10^12)
> > numbers per second (on average) and that you had started your program
> > shortly after the Big Bang, today you would have around 10^8699970
> > numbers left to test.
> > 
> > Big enough yet?
> > 
> > The number has been the record holder for 3 years now. Why do you think
> > that is? I don't mean to discourage your scripting efforts, but this
> > goal seems seriously out of reach with your approach. For a quick
> > comparison, today's statistics for the GIMPS project are
> > 
> >     Teams      864
> >     Users      143,562
> >     CPUs       1,195,522
> >     TFLOP/s    324.606
> >     GHz-Days   162,303
> > 
> > And that's with a specialized algorithm and software optimized to do
> > this one task. If you really are serious about finding prime numbers,
> > you'll have to acquire the mathematical knowledge and familiarize
> > yourself with existing algorithms (or just join GIMPS). And if you're
> > hell-bent on doing it in JavaScript, you will need to learn the basics
> > of the language first.
> > 
> > 
> > - stefan
> 
> 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.

Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer")

[toc] | [prev] | [next] | [standalone]

#29346

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>

[toc] | [prev] | [next] | [standalone]

#29347

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>

Well since i really just was after doing add straighforward 0(n) and use a big base. Interesting to see that finbonacci n can be done in a single step, but i am not sure howto get it to work with my big bases.

My multiplication is quite fast but i shall see if i can improve it.

[toc] | [prev] | [next] | [standalone]

#29348

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.

[toc] | [prev] | [next] | [standalone]

#29349

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. 

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.

1th 2
2th 2
3th 4
4th 8
5th 32
6th 256
7th 8192
8th 2097152
9th 1717,9869184
10th 360,2879701,8963968
11th 618970,196426,9013744,9562112
12th 22,3007451,9853062,3141535,7182726,4836150,5980416
13th 1,3803492,6935811,2757486,9511724,5540509,490221,7944340,7731103,2504844,7598592
14th 30,7828173,4093318,6884593,782,3719828,5218546,3050511,3020933,4604222,669701,3398219,5790167,3955116,2884034,4380178,1174272 

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#29352

On Tuesday, January 19, 2016 at 10:35:20 AM UTC-6, jonas.t...@gmail.com wrote:

> If i just can get the base to be of anysize, i am sure i will be able to multiply in near linear time. 

Doubtful [1]

[1] <https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Multiplication_of_large_integers>

[toc] | [prev] | [next] | [standalone]

#29353

Den tisdag 19 januari 2016 kl. 17:57:37 UTC+1 skrev Michael Haufe (TNO):
> On Tuesday, January 19, 2016 at 10:35:20 AM UTC-6, jonas.t...@gmail.com wrote:
> 
> > If i just can get the base to be of anysize, i am sure i will be able to multiply in near linear time. 
> 
> Doubtful [1]
> 
> [1] <https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Multiplication_of_large_integers>

http://jt.node365.se/fibonacci14.html

[toc] | [prev] | [next] | [standalone]

#29356

Den tisdag 19 januari 2016 kl. 19:18:26 UTC+1 skrev jonas.t...@gmail.com:
> Den tisdag 19 januari 2016 kl. 17:57:37 UTC+1 skrev Michael Haufe (TNO):
> > On Tuesday, January 19, 2016 at 10:35:20 AM UTC-6, jonas.t...@gmail.com wrote:
> > 
> > > If i just can get the base to be of anysize, i am sure i will be able to multiply in near linear time. 
> > 
> > Doubtful [1]
> > 
> > [1] <https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Multiplication_of_large_integers>
> 
> http://jt.node365.se/fibonacci14.html

It seem to work up to base 10^19 without overflow but i am not sure the result comes out correct. I did go ver SQET max integer.

[toc] | [prev] | [next] | [standalone]

#29360

On 01/19/2016 08:34, jonas.thornvall@gmail.com wrote:
> Den tisdag 19 januari 2016 kl. 02:42:22 UTC+1 skrev Stefan Weiss:
>> this goal seems seriously out of reach with your approach.

> But if i really can do the math in quasilinear time i should be able to do it.

Well, I tried. I don't know how to make it any clearer.

The only thing left is to inform you that your goal post has moved.
A few hours ago, the new largest known prime number has been published:
2^74207281 - 1. It has 22338618 decimal digits.
http://www.mersenne.org/primes/?press=M74207281

I won't redo the Big Bang example with the new number. What's a few
million digits more or less when you're about to revolutionize mathematics.

- stefan

[toc] | [prev] | [next] | [standalone]

#29366

Den onsdag 20 januari 2016 kl. 01:33:36 UTC+1 skrev Stefan Weiss:
> On 01/19/2016 08:34, jonas.thornvall@gmail.com wrote:
> > Den tisdag 19 januari 2016 kl. 02:42:22 UTC+1 skrev Stefan Weiss:
> >> this goal seems seriously out of reach with your approach.
> 
> > But if i really can do the math in quasilinear time i should be able to do it.
> 
> Well, I tried. I don't know how to make it any clearer.
> 
> The only thing left is to inform you that your goal post has moved.
> A few hours ago, the new largest known prime number has been published:
> 2^74207281 - 1. It has 22338618 decimal digits.
> http://www.mersenne.org/primes/?press=M74207281
> 
> I won't redo the Big Bang example with the new number. What's a few
> million digits more or less when you're about to revolutionize mathematics.
> 
> - stefan

It seem obvious to me that multiplication can be done in linear time, maybe it is because i've been thinking about if before.

[toc] | [prev] | [next] | [standalone]

#29367

Den onsdag 20 januari 2016 kl. 11:10:28 UTC+1 skrev jonas.t...@gmail.com:
> Den onsdag 20 januari 2016 kl. 01:33:36 UTC+1 skrev Stefan Weiss:
> > On 01/19/2016 08:34, jonas.thornvall@gmail.com wrote:
> > > Den tisdag 19 januari 2016 kl. 02:42:22 UTC+1 skrev Stefan Weiss:
> > >> this goal seems seriously out of reach with your approach.
> > 
> > > But if i really can do the math in quasilinear time i should be able to do it.
> > 
> > Well, I tried. I don't know how to make it any clearer.
> > 
> > The only thing left is to inform you that your goal post has moved.
> > A few hours ago, the new largest known prime number has been published:
> > 2^74207281 - 1. It has 22338618 decimal digits.
> > http://www.mersenne.org/primes/?press=M74207281
> > 
> > I won't redo the Big Bang example with the new number. What's a few
> > million digits more or less when you're about to revolutionize mathematics.
> > 
> > - stefan
> 
> It seem obvious to me that multiplication can be done in linear time, maybe it is because i've been thinking about if before.

In fact it seem so obvious that can wonder how it can escape people, probably it has something todo with the way math is teached.

[toc] | [prev] | [next] | [standalone]

#29368

jonas.thornvall@gmail.com writes:
<snip>
>> It seem obvious to me that multiplication can be done in linear
>> time, maybe it is because i've been thinking about if before.
>
> In fact it seem so obvious that can wonder how it can escape people,
> probably it has something todo with the way math is teached.

All you have to do is describe the algorithm -- you don't even have to
implement it.  If you have a better multiplication algorithm, other
people will implement it everywhere at the drop of a hat.  If, when you
try, you find that no one can understand you, please consider the
possibility that you have confused yourself.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web