[107812] in Cypherpunks
Re: CDR: A digital way to filter... (fwd)
daemon@ATHENA.MIT.EDU (Jim Choate)
Sun Jan 24 19:05:24 1999
From: Jim Choate <ravage@EINSTEIN.ssz.com>
To: cypherpunks@EINSTEIN.ssz.com
Date: Sun, 24 Jan 1999 17:52:42 -0600 (CST)
Reply-To: Jim Choate <ravage@EINSTEIN.ssz.com>
----- Forwarded message from Bill Stewart -----
Date: Sun, 24 Jan 1999 14:30:49 -0800
From: Bill Stewart <bill.stewart@pobox.com>
Subject: Re: CDR: A digital way to filter...
First of all, linear in n is exponential in log2 n,
which is what matters here (assuming you're factoring numbers
on the order of 1024 bits long, rather than numbers up to 1024...)
Also, you need exponentially many counters, so linearity is irrelevant :-)
(Hint: How many primes are less than 2**1024?)
Do you have a particular planet you're planning to store this on?
Of course, once you've built them, how do you distribute n signals
to the k counters, and get the results back?
You could naively do this in linear-with-k time,
but you can get fancier and do it in log k time
(your choice of logarithm base, depending on how much fanout you can support.)
----- End of forwarded message from Bill Stewart -----
It's linear in the sense that it takes me n steps to determine if n is
prime.
Whatever 2^1024 comes out to is the largest value of n and by extension
the biggest number of steps it takes to determine if it's prime.
I don't need exponential counters. I need to a counter set that is the
number of primes less than n. That is, the maximal number of registers
is given by x/ln(x).
For example:
n # primes
10^6 664,579
10^9 50,847,478 (and primes get sparser as the n grows and we don't
know all the primes up to here even)
So we increase the set of potential candidates by 10^3 but the number of
actual candidates only increases by 10^2. Hardly exponential.
So, how many primes registers will we need for 2^1024?
2^1024=10^308.255
2^1024/ln(1^1024)=2.533E305
How long to count at 1M/s pulse rate:
1.714E302 s, 5.44E294 yrs.
Whis comes out to 10E305.4 registers each 1024 bits in length. So the total
number of bits taken up by the registers are:
(10E305.4)(1024)=2.572E308 (ie a 2 with 308 places till the decimal)
Which is how many bytes:
3.215E307
Which is how many gigabytes:
3.215E307/1073741824=2.91E298 G of storage.
Which is how many Terabytes:
2.91E298/1024=2.84E295
As to building them;
Hardware:
I'd build each counter with a reset, increment, end of count alert, and
a zero sum alert. First I'd reset them all. Then drive each register with the
same n pulses. Once I had done n pulses I'd strobe the end of count alert line
which would tell me to signal a zero sum alert. I'd just OR them all together
since any one zero sum is enough to know this isn't prime.
Software:
I'd build a counter object with the same sort of attributes as above.
Hard? Yes. Expensive? Yes. Can we do it today? Probably not. Is it doable?
Yes.
The architecture could be expended so that all the primes could be found on
the way so the sequence wouldn't need to be run but once. Have each register
shadow it's current result. Compare those results at each clock increment
to see if any zero sum's are there. If they are it isn't prime. As you find
the new primes you set new registers to the appropriate modulo and keep
counting.
____________________________________________________________________
What raises the standard of living may well diminish the
quality of life.
The Club of Rome
The Armadillo Group ,::////;::-. James Choate
Austin, Tx /:'///// ``::>/|/ ravage@ssz.com
www.ssz.com .', |||| `/( e\ 512-451-7087
-====~~mm-'`-```-mm --'-
--------------------------------------------------------------------
