Guest
Please any one give me the idea how i can generate prime number in verilog without the use of for loop. i computed in this way that a prime number is not divisible by its previous prime number.
A
Allan Herriman
Guest
On Fri, 26 Dec 2014 08:35:25 -0800, mawais2011 wrote:
Assuming you want this to be synthesisable, may I suggest the Sieve of
Eratosthenes
<http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>
In common with other sieve algorithms, it requires that you know the
upper limit in advance and have enough memory to hold a flag for each
number up to that upper limit. As such, it is not suited to a design
that has to produce a continuous stream of prime numbers without bound.
Allan
Assuming you want this to be synthesisable, may I suggest the Sieve of
Eratosthenes
<http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>
In common with other sieve algorithms, it requires that you know the
upper limit in advance and have enough memory to hold a flag for each
number up to that upper limit. As such, it is not suited to a design
that has to produce a continuous stream of prime numbers without bound.
Allan
T
Tim Wescott
Guest
On Fri, 26 Dec 2014 08:35:25 -0800, mawais2011 wrote:
To what end? Are you looking to synthesize something, or do you need
prime numbers for a test bench?
If you want to end up with hardware that coughs up prime numbers -- I
think you'll either need to settle for a look-up table with stored
numbers, or some some sort of state machine that does a sieve or whatever
it is that people do these days that's more efficient than a sieve.
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
To what end? Are you looking to synthesize something, or do you need
prime numbers for a test bench?
If you want to end up with hardware that coughs up prime numbers -- I
think you'll either need to settle for a look-up table with stored
numbers, or some some sort of state machine that does a sieve or whatever
it is that people do these days that's more efficient than a sieve.
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
T
Tim Wescott
Guest
On Sat, 27 Dec 2014 04:59:51 +0000, Allan Herriman wrote:
Well, a flag for each number up to the square root of the upper limit, if
you really want to be stingy.
Is there _any_ prime-finding algorithm that doesn't require you to store
more and more history as you go, or to repeat calculations that you
wouldn't otherwise have to repeat?
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
Well, a flag for each number up to the square root of the upper limit, if
you really want to be stingy.
Is there _any_ prime-finding algorithm that doesn't require you to store
more and more history as you go, or to repeat calculations that you
wouldn't otherwise have to repeat?
--
Tim Wescott
Wescott Design Services
http://www.wescottdesign.com
G
glen herrmannsfeldt
Guest
Tim Wescott <seemywebsite@myfooter.really> wrote:
Unlike the for loop in C or Java, the verilog for loop increases the
amount of hardware used to do the computation. Very often, that is
not what you want.
(snip)
I would guess not, but you can make it interesting. Find a compromise
between storing and calculating.
My first prime number program was on an HP 9810A calculator. It stored
the values computed so far in addressable registers, and stopped when
it ran out of them. (I didn't yet know about the square root rule.)
Not so much later, I started learning Fortran, and the sample program
in the OS/360 Fortran manual prints a table of primes. That one first
prints out 2 and 3, then loops for odd numbers, testing each by
dividing by values up to sqrt(float
). The program was much smaller
and simpler than I had done on the 9810A.
Note that the Fortran program takes one optimization, after printing 2,
not even trying other even numbers. You could take that one better, as
only two of every six aren't divisible by either 2 or 3. You could write
a loop incrementing by six, with two trial loops inside. Note that
this trades of program size and complexity for time.
You could also extend it using 5, 7, and 11 as previously known primes,
and reduce the computation accordingly.
In the verilog case, you likely don't want hardware with size
proportional to, or maybe even proporional to the square of, the largest
prime value that you want to compute. Most often, that means a state
machine.
You want to loop in time, not space (logic), generating potential
primes and testing them. Seems to me that either the sieve or looping
in a state machine through potential primes, and another loop in
time testing them isn't so complicated to generate, though not the
easiest. You might do it wit a state machine generating tool.
It seems likely that the hardware has to be designed based on the
largest possibly value, as enough bits will have to be supplied to
hold that value. But bits are pretty cheap these days.
You could loop at 50MHz, trying primes, maybe with an iterative
divider. Then stop for 1s when you find one, with its value on
the built-in (to your FPGA board) display.
-- glen
Unlike the for loop in C or Java, the verilog for loop increases the
amount of hardware used to do the computation. Very often, that is
not what you want.
(snip)
I would guess not, but you can make it interesting. Find a compromise
between storing and calculating.
My first prime number program was on an HP 9810A calculator. It stored
the values computed so far in addressable registers, and stopped when
it ran out of them. (I didn't yet know about the square root rule.)
Not so much later, I started learning Fortran, and the sample program
in the OS/360 Fortran manual prints a table of primes. That one first
prints out 2 and 3, then loops for odd numbers, testing each by
dividing by values up to sqrt(float
). The program was much smallerand simpler than I had done on the 9810A.
Note that the Fortran program takes one optimization, after printing 2,
not even trying other even numbers. You could take that one better, as
only two of every six aren't divisible by either 2 or 3. You could write
a loop incrementing by six, with two trial loops inside. Note that
this trades of program size and complexity for time.
You could also extend it using 5, 7, and 11 as previously known primes,
and reduce the computation accordingly.
In the verilog case, you likely don't want hardware with size
proportional to, or maybe even proporional to the square of, the largest
prime value that you want to compute. Most often, that means a state
machine.
You want to loop in time, not space (logic), generating potential
primes and testing them. Seems to me that either the sieve or looping
in a state machine through potential primes, and another loop in
time testing them isn't so complicated to generate, though not the
easiest. You might do it wit a state machine generating tool.
It seems likely that the hardware has to be designed based on the
largest possibly value, as enough bits will have to be supplied to
hold that value. But bits are pretty cheap these days.
You could loop at 50MHz, trying primes, maybe with an iterative
divider. Then stop for 1s when you find one, with its value on
the built-in (to your FPGA board) display.
-- glen
A
Allan Herriman
Guest
On Sat, 27 Dec 2014 19:00:48 -0600, Tim Wescott wrote:
Yes, they're called "incremental sieves". I've never tried one.
The crypto folk (well, those still using RSA) generate their big primes
by generating random numbers then testing them.
Generating big random numbers is quick, and the primality test is pretty
quick too (particularly if one can trade off accuracy and let a
pseudoprime through occasionally).
Regards,
Allan
Yes, they're called "incremental sieves". I've never tried one.
The crypto folk (well, those still using RSA) generate their big primes
by generating random numbers then testing them.
Generating big random numbers is quick, and the primality test is pretty
quick too (particularly if one can trade off accuracy and let a
pseudoprime through occasionally).
Regards,
Allan
N
Nils
Guest
On 12/28/2014 03:24 AM, Allan Herriman wrote:
That's indeed how the crypto folks do it. The Miller-Rabin test uses
little memory, is fast and not to hard to implement.
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
As you said the algorithm will indeed let a pseudoprime through, but you
have control over how often that happens on average.
I just looked up the numbers in the book Cryptographic Engineering by
Bruce Schneider et. al.
He states that just 64 random Miller-Rabin tests are enough to lower the
chances of a pseudoprime down to 2^-128 percent. He also states that the
chance of getting killed by a meteor while reading this sentence is far
larger than that.
/Nils
That's indeed how the crypto folks do it. The Miller-Rabin test uses
little memory, is fast and not to hard to implement.
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
As you said the algorithm will indeed let a pseudoprime through, but you
have control over how often that happens on average.
I just looked up the numbers in the book Cryptographic Engineering by
Bruce Schneider et. al.
He states that just 64 random Miller-Rabin tests are enough to lower the
chances of a pseudoprime down to 2^-128 percent. He also states that the
chance of getting killed by a meteor while reading this sentence is far
larger than that.
/Nils