tables of p(n) and/or pi(n) / tables of primes
cino hilliard
hillcino368 at hotmail.com
Tue Dec 20 22:27:51 CET 2005
Hi Hugo,Hans and seqfans
>From: "Pfoertner, Hugo" <Hugo.Pfoertner at muc.mtu.de>
>To: seqfan at ext.jussieu.fr
>Subject: RE: tables of p(n) and/or pi(n) / tables of primes
>Date: Wed, 21 Sep 2005 16:27:32 +0200
>
>-----Original Message-----
>From: cino hilliard [mailto:hillcino368 at hotmail.com]
>Sent: Wednesday, September 21, 2005 01:47
>To: seqfan at ext.jussieu.fr
>Cc: cinohill at hotmail.com
>Subject: Re: tables of p(n) and/or pi(n) / tables of primes
>
> >From: Hans Havermann <pxp at rogers.com>
> >To: seqfan at ext.jussieu.fr
> >Subject: Re: tables of p(n) and/or pi(n) / tables of primes
> >Date: Mon, 19 Sep 2005 11:26:57 -0400
> >
> >On Sep 19, 2005, at 6:53 AM, cino hilliard wrote:
> >
> >>I have computed and stored all primes < 100 billion in a 45 gig file.
I finally computed and saved enough primes to get A099824(10)
This is updated to primes < 260 billion in file
12/19/2005 06:40 AM 82,406,594,024 prime2-260bill.bin
These numbers are 8 bytes binary and are read and summed by a power basic
program dll. C
cannot read beyond 2^31-1 bytes. The dll is declared in a bcx program and
translated to LccWin32
using the 100 digit precision qfloat to get the proper output.
Here are some timings including A099824(10). The sumprimes dll reads blocks
of 1000 from the file
prime2-260bill.bin giving faster access.
num 1000000
7472966967499.0000000000000000000000000000
Time 0.8125s
Hugo fortran time 0.57s
num 10000000
870530414842019.00000000000000000000000000
Time 1.703125s
Hugo fortran time 4.28s
num 100000000
99262851056183695.000000000000000000000000
Time 16.6875s
Hugo fortran time 45.67s
num 1000000000
11138479445180240497.000000000000000000000
Time 170.4063s
Hugo fortran time ? 4500s ?
num 10000000000
1234379338586942892505.0000000000000000000
Time 2042.953s (While multi-tasking. Should be 1800 straight through)
Hugo fortran time ? 45000s ?
Well in all fairness, I must admit it took a few months to create the
prime2-260bill.bin file using
Pari creating chunks of 10 billion 11 digit numbers and then converting to
64 bits and copying
in dos /B +. However, once it is in stone, we are free to read it.
> >How much extra time would the base conversion/compression add to
>accessing
> >the database for real-time arithmetic? For example, how long would it
>take
> >you to sum the first billion primes?
The fragment below compresses the the string translation from reading the
binary 8 byte
long long data from prime2-260bill.bin. The reading of primes direct is
about 10 times faster
than reading compressed data and converting it. The conversion routine is
the base$() function
in cvbase.bas. If we can streamline this function we can get some better
times on converting
compressed data back to org. For the 1 mill primes from 10 billion to 10
billion + 1 mill we have
a 5 million byte compressed file compared to a 12 million byte wall to wall
prime file. This is 42%
the size. So for the next level A099824(11), we will need all of the the
primes <= 2,760,727,302,517. At 13 bytes we are talking 35 terabytes of raw
storage. and 6/13 = 46% =
16 terabytes compressed. Obviously this will require a community effort.
Recall reading a terabyte
one byte per second will take 31,700 years. So 1 millisecond access speed
will take 31.7 years.
what is comming - solid state storage or drives. This is a preample to what
we will be able to do.
The largest prime database I know is the N'th prime page which is fantastic
however it is too slow
on line.
Perhaps someone has a sieve that will produce A099824(10)?
I now go out on a limb.
Some observations:
Because of the almost constant time required to random access any record in
a file, sooner or later,
reading primes this way will be faster than ANY sieve program in the long
run. Of course I do not
count the time required to get the prime records on disk.
Perhaps someone can prove this or show that it cannot be.
There is Moore's law about density of processor capability doubling every x
months. Can a
similar law be extrapolated with regard to prime number finders and prime
factoring algorithms?
As I recall Martin Gardner once remarked that a certain composite number was
safe for a few
quadrillion years and it was later factored.
Merry Christmas
Cino
***********************Program Fragment*************************************
Cvbase.bas
dim digits$[256],j,k,zero$,fil$,fil2$,fil3$
zero$="0"
k=1
for j =48 to 57 'append ascii codes 48-57 ,0-9
digits$[k] = chr$(j)
k++
next
for j = 65 to 90 'append ascii codes 65-90 A-Z keep with
Caps A-F for hex
digits$[k] = chr$(j)
k++
next
for j = 97 to 122 'append ascii codes 97-122 a-z
digits$[k] = chr$(j)
k++
next
for j = 58 to 64 'Append 58-64
digits$[k] = chr$(j)
k++
next
for j = 91 to 96 'append ascii codes 91-96
digits$[k] = chr$(j)
k++
next
for j = 123 to 255 'append ascii codes 123-255
digits$[k] = chr$(j)
k++
next
for j = 0 to 9 'append ascii codes 0-9
digits$[k] = chr$(j)
k++
next
for j = 14 to 47 'append ascii codes 14-47
digits$[k] = chr$(j)
k++
next
function base$(r1,r2,num$) 'This is the crown jewel for numeric data
compression
dim RDX$,asci,Q,j,ln,p,i,d$,c,k,zero$
!long double pwr,dec,dec2,Qq,lnq,r1q,r2q,kq;
r1q=r1
r2q=r2
dec=0
ln = len(num$)
RDX$=""
for j = 1 to ln
d$=mid$(num$,j,1)
c=0
do
c++
loop until d$ = digits$[c] 'Get code assigned to digits$[]
above
asci = c-1
lnq =ln-j
dec += asci*pow(r1q,lnq) 'Convert the num in r1 to
decimal
next
j=1
while mid$(num$,j,1) = zero$
RDX$=RDX$ & zero$
j++
wend
j=0
dec2=dec
while dec2 > 0
dec2 = floor(dec2/r2q)
j = j+1
wend
for k = j-1 to 0 step -1
pwr = pow(r2q,k) 'This is just going from base 10 to another
base.
Qq = dec / pwr 'converting the decimal number to r2 which
in effect
Q=Qq
dec = dec - pwr*Q 'is converting num in base r1 to a number in
base r2.
RDX$ = RDX$ & digits$[Q+1] 'call globally declared digits[] character
base
' RDX$ = RDX$ & str$(Q) & "," 'Maple style.
next
function = RDX$
end function
More information about the SeqFan
mailing list