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

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

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.

We weren't talking about multiples of 2

******64, we were talking about

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/

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

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:

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

#!/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

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

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

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.

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

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

#### Site Timeline

- » hash slice surprise
- — Next thread in » PERL Discussions

- » Perldancer isolation
- — Previous thread in » PERL Discussions

- » s suffix question
- — Newest thread in » PERL Discussions

- » Dell Battery Slice LED codes
- — The site's Newest Thread. Posted in » Laptop Computers Forum