simple algorithm for finding primes

[osmium]

Re: simple algorithm for finding primes


Richard Heathfield <dontmail@addre ss.co.uk.invali d> wrote in message
news:brbmj6$i2m $1@hercules.bti nternet.com...[color=blue]
> osmium wrote:
>[color=green]
> > Richard Heathfield writes:
> >[color=darkred]
> >>
> >> Actually, it isn't all that difficult to make bignums portable. There
> >> is no particular reason why you shouldn't be able to implement, say,
> >> RSA using code that will work on any conforming hosted implementation
> >> (and, indeed, on freestanding implementations if they have the RAM
> >> for it; if you have a few kilobytes, you can do it).[/color]
> >
> > I am just an innocent bystander here. But you, Richard, seem to be
> > comparing a program that *could* be written with one that *has* been
> > written.[/color]
>
> Well, if he'd written a portable bignum program already, he'd have said[/color]
so,[color=blue]
> wouldn't he?
>[color=green]
> > I notice you always refer to bignum in the future tense. If you
> > are speaking of an actual library it most likely has an actual name and[/color][/color]
a[color=blue][color=green]
> > parent. My guess is that is where the alleged hypocrisy comes in.[/color]
>
> Ah, I see. Well, we already have Miracl and GMP, do we not? And yes, I[/color]
have[color=blue]
> my own bignum library, which works (except for Rabin-Miller, which I hope
> to fix today), but which is still a bit untidy, which is why I haven't
> published it yet. The fastest in the world it ain't (because the emphasis
> is on readability and portability), but it's fast enough that it is
> unlikely to be the bottleneck in typical usages.
>[color=green]
> > If I were to write a reasonably fast bignum library I would sure like to
> > see that well hidden carry bit.[/color]
>
> Perhaps I'm talking through ignorance here, despite having written one
> myself, but why would anyone need to *hide* a carry bit?[/color]

From the Miracl page:

"MIRACL is compact, fast and efficient and its
now easier than ever to get the same near-optimal
performance from any processor. Although
essentially a portable library, inline assembly
and special techniques can be invoked for
blistering speed"

It would seem to me that the designers of Miracl also wanted to see that
carry out bit which the designers of the C language hid. And the inline
assembly destroys the portability. It is not clear to me that a sensible,
fast, binary, arithmetic big numbers library is possible. I say binary to
exclude BCD arithmetic which is a different kettle of fish. I read
"blistering speed" as meaning reasonably fast.

I will let someone else research GMP. My algorithm is first in, first out.

If I were designing C, I would have considered adding the carry out (and
perhaps other things) as a standard signal. But even so, the resulting big
numbers library would still be slower than necessary.

[Wolfgang Riedel]

Re: simple algorithm for finding primes

Paul Hsieh wrote:[color=blue]
>
> Arthur J. O'Dwyer says...[color=green]
> > On Wed, 10 Dec 2003, Richard Heathfield wrote:[color=darkred]
> > > Paul Hsieh wrote:
> > > > Arthur J. O'Dwyer says:[/color][/color][/color]
<snip>[color=blue][color=green]
> > Richard, in his flamboyant way, suggests bignums. :)[/color]
>
> No -- in his *hyppocritical* way, he suggest bignums.[/color]

Paul,

maybe, he has every right, to be critical of hippos?!

Btw., I think, you do yourself no good with those hypocritical
ad hominem attacks.

Let's stay civilized.

Wolfgang

<snip>[color=blue]
> --
> Paul Hsieh
> http://www.pobox.com/~qed/
> http://bstring.sf.net/[/color]

[Chris Torek]

Re: simple algorithm for finding primes

In article <brcbcj$1qdvv$1 @ID-179017.news.uni-berlin.de>
osmium <r124c4u102@com cast.net> writes:[color=blue]
>If I were designing C, I would have considered adding the carry out (and
>perhaps other things) as a standard signal.[/color]

Carry-out of unsigned addition of two operands is trivial to pick
up:

unsigned long a, b, result;
int carry;

result = a + b;
carry = result < a; /* or result < b */

In assembly languages for CPUs without carry flags (e.g., MIPS),
this C code is often a direct translation of the required
assembly code:

addu rRESULT, rA, RB # set register RESULT = A + B
slt rCARRY, rRESULT, rA # set register CARRY = RESULT < A

and on CPUs with carry flags, a compiler should be able to optimize
the "carry = " operation appropriately. If the carry is then fed
into a subsequent op:

r2 = a2 + b2 + carry;

it should even be able to emit an "ADC" instruction, if one exists.
Of course, obtaining carry-out of 3-or-more operand add instructions
is more difficult to achieve, but quite a few modern CPUs have no
three-operand-input operations (including no "add with carry"
instructions; indeed, MIPS, as mentioned above, has no carry flag
at all). Still:

carry = r2 < a2 || (r2 == a2 && carry);
/* or equivalently, carry = (r2 < a2) | ((r2 == a2) & carry); */

(since "carry" is either 0 or 1 initially).

(Whether your compiler does such optimizations is another question
entirely. If those optimizations are important to you, I suggest
that you could put some time, money, and/or effort into seeking
out -- or creating, e.g., by modifying gcc -- compilers that do
them.)

(V9 SPARC points out one reason MIPS does not have a carry flag.
V8 and earlier had only the "condition codes" register, %cc, with
the usual four condition codes: N V C and Z => negative, overflow,
carry, and zero. V9 has %icc, the 32-bit condition codes, and
%xcc, the 64-bit condition codes. A 64-bit register holding a
result of 0x0000000087654 321 is negative in 32-bits, but positive
in 64-bits. The sum of 0x00000000fffff fff and 0x00000000fffff fff
is 0x00000001fffff ffe, which has no carry in 64-bits but a carry
in 32-bits.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.