Kids can do math better than x86 cpu's.

Were they? Did Greeks really had so advanced arithmetic skills?

library...

It should be noted, all modern CPU I know of have these primitives, even the lowly PIC. So bignum math is supported by hardware *already*. The problem is higher level languages like C doesn't support these low level hardware features. Like, how would you detect the carry bit in C?

Using add with carry is easy in C, various compilers can detect it:

x = y + z; if (x < y) x++; x += a;

Translates to:

ADDS x, y, z ADC x, x, a

Many compilers also detect NxN -> 2N bit multiplies.

Wilco

Did you take into account the number of transistors needed for each method ?

Maybe the methods you mentioned require less steps but because it's a complexer method it requires more transistors !

Since the simpler method requires less transistors it can be implemented more in parallel on the same "chip space".

So to make comparision fair that factor has to be taken into the equation as well for example:

1. "Reaction time of simple method" versus "Reaction time of complex method".

Plus:

1. "Throughput of all sequentially called parallel implemented simple methods" versus "Throughput of all sequentially called parallel implemented complex methods".

For example:

The complex method has reaction time of 1000 nanoseconds.

The simple method has reaction time of 50000 nanoseconds.

The complex method can be implemented 10 times on chip space.

The simple method can be implemented 1000 times on chip space.

Throughput for one complex method: 1 000 000 000 / 1 000 = 1 000 000

Throughput for one simple method: 1 000 000 000 / 50 000 = 20 000

Total throughput complex method: 1 000 000 * 10 = 10 000 000

Total throughput simple method: 20 000 * 1 000 = 20 000 000

This example shows the simple method could outperform the complex method.

Bye, Skybuck.

Not that I can see. How many have a 64x64->128 multiply and a

|> Using add with carry is easy in C, various compilers can detect it:

Some compilers may be able to, IF you use a code form that they can recognise; but, if they don't document that and exactly what code forms are acceptable, you are just hoping.

And, in any case, that is not "in C" - it is "in Intel C" or "in gcc" etc. There is no way of doing it in standard or portable C, let alone standard AND portable C.

Regards, Nick Maclaren.

Un bel giorno Skybuck Flying digitò:

In my opinion tasks like this don't belong to the CPU instruction set, but to the software level. The CPU instructions should address all (and just) the useful tasks that can't be done with a comparable efficiency with a group of instructions, for example HW multiplication between two registers in one cycle, MAC in one cycle, and so on.

This is nonsensical. You wouldn't implement such methods purely in hardware since, unless you've got a way of adding transistors at run-time, you'd be constrained in the size of number you could deal with.

So, you're necessarily looking at a software implementation, perhaps assisted by some carefully chosen hardware primitives. As far as I know, no-one has come up with primitives that are any better than the universal notions of fixed-size arithmetic and carry bits.

What, you thought the Romans invented it? You ever try doing long division with Roman Numerals, man? (OK, the other number systems in use weren't much better!)

More realistically, while arithmetic is a greek word, most texts trace the algorithms taught in grade school today to the Indian mathematician Brahmagupta. He called his method of multiplication gomutrika, which translates to (I'm not making this up) "trajectory of a cow's urine".

Tim.

Widening multiplies are quite common on CPUs, division is far less common (ie. on RISC), especially the narrowing form. Luckily you don't need a division primitive for multi precision arithmetic.

The idioms for rotate, widening multiplies, carry, multiply+accumulate, divison+modulo and so on are pretty standard. It is trivial to recognise the various forms, eg. a + b a + b both test the carry flag.

In article , "Wilco Dijkstra" writes: |> |> > Not that I can see. How many have a 64x64->128 multiply and a |> > 128/64->64,64 quotient, remainder? |> |> Widening multiplies are quite common on CPUs, division is far less |> common (ie. on RISC), especially the narrowing form. Luckily you don't |> need a division primitive for multi precision arithmetic.

No, you don't. You DO, however, need it for efficient, relatively short, multiple precision arithmetic - such as is very common, especially for floating-point emulation.

And you are wrong that widening multiplies are quite common for the largest efficient integer sizes. It gains you very little having to drop to a size down in order to get them.

|> > |> Using add with carry is easy in C, various compilers can detect it: |> >

|> > Some compilers may be able to, IF you use a code form that they can |> > recognise; but, if they don't document that and exactly what code |> > forms are acceptable, you are just hoping. |> |> The idioms for rotate, widening multiplies, carry, multiply+accumulate, |> divison+modulo and so on are pretty standard. It is trivial to recognise |> the various forms, eg. a + b a + b both test the carry flag.

The add algorithm needs 1 digit for A, 1 digit for B and two digits for the result.

Maybe some more digits for the operation and that's about it.

The digits of A and digits of B and the result digits for C can all be streamed in and out to and from memory.

Lol,

Welcome to Skybuck's World =D where the seemingly impossible becomes possible =D

Note:

You asked about the ADD method and that's the only thing I discussed above, for the other 3 algorithms I don't know... I assume the other three algorithms can be implemented with ADD.

Bye, Skybuck.

Terje Mathisen spake the secret code thusly:

I don't understand your objection. You can implement multipliers in FPGAs, plenty of people have. For arbitrary precision arithmetic you might find a bit-serial approach easier to implement on an FPGA. That means you can probably have several multipliers running concurrently.

"Ken Hagan" spake the secret code thusly:

There's nothing that says the hardware has to process all the bits of an arbitrary precision number in parallel. It can process them in chunks. Of course, you might argue that this is just what the software is doing and you'd be right, but it would still be an implementation in hardware.

The midsize Xilinx chips have dozens of hard multipliers. And you can make lots more, if slower, from the regular logic cells.

John

The problem is that a 17x17->34 unsigned multiplier clocked at 500MHz is really only 1/64 as useful as a 64x64->128 multiplier clocked at

Xilinx chips start comparable in price with Core2 processors and get absurdly expensive very quickly. A Virtex-5 LX50 board costs $900, and that gets you 48 multipliers.

Tom

Not really.

Using general FPGA cells to implement a multiplier will be _far_ from efficient compared with a dedicates slice of silicon.

Bignum math is either trivial (no efficiency/speed requirements), or critical.

In the latter case FPGAs are unsuited.

See above.

I guarantee you that this will be significantly slower than quite simple x86 code using the basic 64x64->128 bitMUL opcode.

Terje

Terje Mathisen spake the secret code thusly:

Nothing says that you can't hook up a dedicated multiplier.

I remain unconvinced just because you state it to be so.

OK, so prove it to me.

Thomas Womack wrote in news:UEe* snipped-for-privacy@news.chiark.greenend.org.uk:

snip

But they all do math better than children. Faster and less prone to errors...

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----

----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Some early responses started approaching the correct answer to SF's initial statement, but then we got off to a lot of wrangling over what is the best approach to solving the problem.

The correct response to your comment, Skybuck, is "of course it can". In fact CPU's from the earliest days of computing have been doing since the '60's, and even before, exactly what 4th-graders do, in the only way possible, since we can't build infinitely wide-word cpu's, and kids (even geniuses) can't keep track of infinite numbers of digits in their heads. Or even arbitrarily large numbers of digits.

Your comment, while it has sparked some interesting discussion, was patently silly from the start.

John Perry