# prime - Page 2

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
•  prime
• George Mpouras
• 10-15-2014

## Re: prime

That's obvious. But what does the number mean(*) and why do you compute it
and what does it have to do with your claim 'that computability in
plain C depends on "plural" typically meaning less than 45'?

(*) I know of course what it means (I did get my estimate of 4.16*10^17
primes somewhere, you know), but that meaning doesn't fit into your
claim at all. Indeed it reminds me of an anecdote (supposedly true,
not a joke):

A maths teacher gave his class the following test: "The school bus
starts empty. At the first stop, it is boarded by 12 pupils. At the
second stop, another 16 get on, and 7 get off, at the third stop 11
get on the bus. We are now at the fourth and final stop. How old is
the driver?" A majority of the pupils answered "32".

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

## Re: prime

On 17.10.14 19:45, Peter J. Holzer wrote:

The number 45 is less disconnected:

- if phrases "gigabytes of primes" etc are understood to be about measuring
the number of primes, not the size of any one prime, this understanding
means that the algorithm needs to count primes as well as compute them;

- computing this result using machine ints implies---here is the
indirection---that we can only count up to a number of primes,
no matter how these are computed.

Silly and trivial as it will seem, the 45 connects thus to an estimate of
possible meanings of the plural of prime number whenever 64 bit uints store
the plural: higher counts do not exist. This alone will limit what can be
computed in plain C, or else one needs some other coding of higher numbers.
(Or, one doesn't need, actually, insofar as computing enough prime does
not require it in the first place, "enough" meaning that the plural be
way below 45 times what's in the first 2^64.)

Now, there is likely more fun in school buses.

## Re: prime

At least it is a number which can be used while computing the solution
to the problem. But your use of it was so wrong that it betrayed a lack
of understanding only marginally less bad than that of the pupils.

Neither. "Gigabytes of primes" can only refer to the combined size of
the primes. "byte" is a unit of size.

Just like "tons of apples" doesn't refer to the number of apples or the
the weight of an individual apple but to the combined weight of a large
number of them.

Actually, it doesn't. It just has to store them. Then you can measure
the size of the output directly. (Actually, I'd say that an algorithm
which doesn't actually output the primes but only counts them doesn't
produce "gigabytes of primes" - it just produces a single number, which
is most likely neither gigabytes long nor a prime).

The largest prime we can compute using 64 bit numbers will be close to
2**64.

Right, but it's the other way around. About every 45th integer in
[0..2**64] is a prime. So the maximum[1] number of primes we can find
with 64 bit numbers is 1/45 of 2**64, not 45 times something.

multiples of "gigabyte". The term "gigabyte" has a well-defined
meaning[2], you can't just play Humpty Dumpty with it[3]. And no matter
how you turn it, there are a lot more than 45 gigabytes of primes you
can compute with 64 bit numbers.

So you put that factor of 45 into the enumerator instead of the
denominator and you mixed up 2**64 with "gigabyte" (what's a factor of
18 billion and the wrong unit between friends?).

hp

[1] Actually, the maximum is somewhat higher, since the N/ln(N) is
asymptotic to the true number from below.
[2] Or four of them, if you combine the two meanings of "giga" with the
two meanings of "byte".
[3] Well, you can. But don't expect anybody to play along.

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

## Re: prime

El 18/10/14 a las 18:14, Peter J. Holzer escribió:

Just in that sense I wrote gigabytes. When a commodity is cheap it's
measured by weight, in Tons.

Well, it must be a big discussion if a certain prime, key of a
cryptographic message, is cheap or not. Certainly not, but
for "unsigned long int" types, It must be.

As the wikipedia says, "As of April 2014, the largest known prime number
has 17,425,170 decimal digits."

--
http://www.telecable.es/personales/gamo/

## Re: prime

El 16/10/14 a las 13:40, G.B. escribió:

I really want that you were right, but it's a clever no, no,
in practical test, and in both VM that runs perl6... it's
a lot slower than perl5.

--
http://www.telecable.es/personales/gamo/

## Re: prime

On 16.10.14 21:28, gamo wrote:

Yes, I should have clarified I was thinking about VMs that

## Re: prime

I've written Factoral 1000 in Basic and in Assembly and Perl.
Basic converted on the fly took 11.5 hours for full precision integer
with all zeros and all digits. It printed on a 132 sheet paper in 10
pitch.  Full sheet.

Assembly in 3 hours.  I based the assembly loosely on the method I used
in Basic.
Both of those were with an 8080 processor. 2 MHz.   Not bad for '76.

I did factorial 1000 in three seconds with my i7
◦CPU_Name: Intel(R) Core(TM) i7-4960X CPU @ 3.60GHz
32 GB of memory.

The process I did back in '76 was to use an array.  Each digit of the
number is an array cell.  Each cell had a value of 0 to 9.  If greater,
one simple works it down the array.

The trick was to generate the array of a size needed.  During
development, it took several tries until I remembered I had a
exponential version in a table book from the Government Printing office.
Sizing it was easy enough once the magnitude of the number was determined.

Martin

On 10/16/2014 6:40 AM, G.B. wrote:

## Re: prime

El 17/10/14 a las 06:13, Martin Eastburn escribió:

You must be refering to factorial of 10000 or higher.

--
http://www.telecable.es/personales/gamo/

## Re: prime

#!/usr/bin/perl
use warnings;
use strict;
use bigint;
use v5.10;

my \$f = 1;
for (2 .. 1000) {
\$f *= \$_;
}

say \$f;

0.15 seconds on a 1.85 GHz Core2 Duo.

That sounds about right for the run time, but it's more than "1 full
sheet" of paper (but then factorial 1000 is less than that).

My guess is that Martin's multiprecision routines are a lot slower than
those in modern libraries (for example he mentioned decimal arithetic,
while GMP uses 32 or even 64 bit chunks).

hp

--
_  | Peter J. Holzer    | Fluch der elektronischen Textverarbeitung:
|_|_) |                    | Man feilt solange an seinen Text um, bis
| |   | hjp@hjp.at         | die Satzbestandteile des Satzes nicht mehr
__/   | http://www.hjp.at/ | zusammenpaßt. -- Ralph Babel

## Re: prime

On 10/17/2014 4:03 AM, gamo wrote:

In Perl - yes I was.  1000 was to easy to seem to be a test.

Martin

## Re: prime

You're assigning the value '1' to \$found and \$ok...

... then immediately assigning them again. For a program that's going
to iterate a very large number of times you might want to save every
clock cycle you can.

my \$found = 1;
my (\$number, \$ok);

or

my (\$found, \$number, \$ok) = (1);

I have no idea how these will compare over a significant number of
iterations, but searches for primes tend to iterate a very large
number of times, I'm sure there must be some saving. Not to mention
how it looks.

Justin.

--
Justin C, by the sea.

## Re: prime

In our last episode, the evil Dr. Lacto had captured our hero,

I'm pretty sure that you can stop checking at int(sqrt(x)), rather than x-1 .

I'm also pretty sure there's a proof, but I can't find it right now.

--hymie!    http://lactose.homelinux.net/~hymie hymie@lactose.homelinux.net
-------------------------------------------------------------------------------

## Re: prime

El 16/10/14 a las 14:38, hymie! escribió:

...

Here

http://stackoverflow.com/questions/5811151/why-do-we-check-upto-the-square-root-of-a-prime-number-to-determine-if-it-is-pri

--
http://www.telecable.es/personales/gamo/

## Re: prime

Each factor f of a number x, such that f <= sqrt(x), pairs
pairs with another number g, also a factor of x, such that
f * g = x and g > sqrt(x).

We know that g exists such that f * g = x because that's the definition
of what it means for f to be a factor of x. This other number g
is also a factor, by the symmetric definition of the product.

We know that g >= sqrt(x) because if we suppose the opposite, namely
that g < sqrt(x), then since f <= sqrt(x), then f * g < sqrt(x) * sqrt(x).
But sqrt(x) * sqrt(x) = x, and so f * g < x, which contradicts f * g = x.

This works in reverse also. Using a similar argument, we can show that each
factor g > sqrt(x) pairs with some f <= sqrt(x).

In other words, given two positive integers f and g (or real numbers, for
that matter) such that f * g = x: we have only these three possibilities:

f = sqrt(x) and g = sqrt(x)
f > sqrt(x) and g < sqrt(x)
f < sqrt(x) and g > sqrt(x)

Thus:

* If we look for factors of x, and do not find any up to sqrt(x),
we are done: there are no factors above sqrt(x) either: the number
is prime.

* If we are looking to discover and list all the factors of a composite number
x, we just need to discover the ones up to sqrt(x). Then for each factor f
thus discovered, we calculate x / f, to obtain the remaining factors.

We do not have to search the space above sqrt(x) which is much
larger than the space below, and asymptotically slower to search.

clever !

## Re: prime

# the simple approach with sqrt is much faster.

sub Find_the_prime_numbers_upto
{
return if \$_[0]<2;
my (\$found,\$N)=1; # say 2;

for (1 .. int (\$_[0]-1)/2)
{
\$N = 2*\$_ + 1;

for (3 .. sqrt \$N)
{
\$N=0, last unless \$N % \$_
}

\$found++ if \$N      # ;say \$N if \$N
}
\$found
}

## Re: prime

George, can you please explain this thing with the comma?

It looks like \$N is being set to zero if (\$N % \$_) == 0, i.e. if the unless fails but I don't
know why?  Thanks.

John Black

## Re: prime

There's a statement here (an expression statement, to be precised) which
is

\$N=0, last

The , evaluates its left-hand argument and discards any value returned
by that, followed be evaluating the right-hand argument and returning
whatever value that returned. The left-hand argument is

\$N=0

hence, evaluating that sets \$N to 0 and the right-hand argument is

last

evaluating that terminates execution of the current block (the
for (3 .. sqrt \$N) { } loop in this case.

This statement has a statement modifier attached which is

unless \$N % \$_

meaning, the \$N=0, last is only executed if \$N % \$_ returns a value
which counts as 'false'. % returns 0 (which counts as false) in case the
left argument was evenly divisible by the right (no remainder), hence,
the complete statements means

"if \$N is evenly divisible by \$_, set \$N to 0 and exit the loop"

## Re: prime

rweikusat@mobileactivedefense.com says...

You are saying it does the left side first "followed by evaluating the right" side.  But if
it did that, it would set \$N to 0 before noticing that the right side has a modifier so it
can't really work that way.  If the "unless" fails, then \$N is not being set to 0 so the left
side must be executed *after* the right side, and somehow NOT be executed if the statement on
the right fails?

John Black

## Re: prime

You're misunderstanding this.

\$N=0, last

is the statement and the modifier applies to that.