Kids can do math better than x86 cpu's.

I spent my high-school years playing with photomultipliers and tunnel diodes and surplus radars and stuff, so I never did learn to program. That hasn't stopped me from writing a million lines or so of code.

John

No, not millions of calculations.

Just one calculation:

78673862876823144124298762947639845862359836963459364589364598376598365892376523978653876432231342132112121265121236721371278157834253482374584582348236583483458723054095409854709850985470985705968705968705968754096875409875409870457854097845069854097856098348572357862352364528761431654126541

Try calculating that in your spreadsheet or x86/x64 processor.

The processor can't do it without help of software/algorithms but your neighbor's kids can all by themselfes !

Conclusion: processor is missing the basics of math, kids do have the basics of math.

Bye, Skybuck.

Kids use algorithms. But no kid is going to do your multiply successfully.

John

But is that a fair comparison? The kid had to be taught some algorithm for doing long division, no? Isn't that in some sense analogous to software for arbitrary-precision arithmetic on a processor that doesn't directly support it?

In article , legalize+ snipped-for-privacy@mail.xmission.com (Richard) writes: |>

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

|> >In the latter case FPGAs are unsuited. |> |> I remain unconvinced just because you state it to be so.

In which case, I won't bother to say that Terje is right, because you won't take any notice.

|> >I guarantee you that this will be significantly slower than quite simple |> >x86 code using the basic 64x64->128 bitMUL opcode. |> |> OK, so prove it to me.

Why? We are not paid to educate you, and we are not inclined to do so if you don't want to learn.

Regards, Nick Maclaren.

"Skybuck Flying" wrote in news:espvlc$mmr$ snipped-for-privacy@news5.zwoll.ov.home.nl:

Hey dopey, kids can't do it without an algorithm either....

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

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

snipped-for-privacy@cus.cam.ac.uk (Nick Maclaren) spake the secret code thusly:

Your arguments are essentially an "appeal to authority", which is why I don't find them convincing. If its so trivial to prove the assertion, then I don't see why this would be a problem.

I didn't ask you to educate me; the assertion was made that FPGAs would be horrible for this and I'm interested to know why. If the response to my "Why?" is just "I'm not going to be bothered explaining it, even in the briefest of terms" then I don't see why I should put much stock in your argument.

If you want to be a crufty curmudgeon, that's certainly your prerogative, but it doesn't make for a convincing defense of the assertion.

Throughput wasn't on the table before...

The question of throughput makes for a much more complex question. It may in some cases be possible to build a very small, but very slow, multiplier and you might get the best throughput per transistor that way. For example, a bit serial multiplier will be of size N, but will take N**2 time to multiply two numbers. A full multiplier (using the basic algorithm) will be of size N**2, but will multiply in approximately log(N)**2.

Also, since we're talking about hardware implementations, pipelining has to be considered. The simply full multiplier can easily be pipelined so that about log(N) multiplications can be working their way though it at any one time.

Now as to particular implementations. Building a full Karatsuba multiplier would be straightforward, and would have about the same advantage in transistor count (modulo some constant) over the basic algorithm as does the software implementation. It would even be pipelineable. You will definitely lose something in die area, since the resulting structure will not be anywhere near as regular as that for a basic full multiplier, so you wouldn't be able to fit as many on a chip.

The transforms needed for FFT multiplication would require a fair bit of analysis before I'd be willing to speculate on how hard it would be to implement a "full FFT multiplier." But as a basic rule, the amount of hardware you need for a "full" implementation will be roughly proportional to the number of operations performed by the algorithm.

But the question is, would you ever choose to build a 1024x1024 bit multiplier in hardware directly? It's possible that might be the best approach for some application, but doesn't solve the problem for numbers bigger than 1024 bits, and will be very expensive in terms of area. Almost certainly you'd build a high precision multiplier out of some smaller components, like a 32x32 multiplier, storage for the work fields, and some control logic, etc. The control logic then replaces the software algorithm, and other than some linear improvements in efficiency (for example, the multiplier might pipeline, you might be able to merge several add functions into a single clock cycle), runs in exactly the same way. And mind you that you can fit a quite complex sequencer in the same space as a 32x32 multiplier.

In any event, it seem difficult to justify any really large hardware multipliers. At some point, the software overhead of a extended precision calculation becomes insignificant. If the CPU actually provided a reasonably fast 1024x1024 multiplier, you could probably write a 16384x16384 multiplier in interpreted Basic (using the hardware 1024x1024 multiplier as a primitive) that would be performance indistinguishable from a hardware or microcode implementation of the same thing. So why burden the hardware with that? Which brings us to your original point. A CPU should not be expected to solve all of the worlds computation problems directly. It should, however, provide a good set of primitives that allow the programmer to solve those problems. Why, for example, should processor have primitive to compute hyperbolic trig functions, or directly handle complex numbers (or any of an infinity of other complex functions)? While at some point it may make sense to include those, for the foreseeable future, implementing those directly in hardware would bring modest performance gains (at best), for considerable complexity, and be applicable only to a small user community.

As a general comment, I can't think of a single CPU that's directly implemented arbitrary precision arithmetic. A few cases of specialized hardware, for example the modular exponentiation unit on Niagara, do exist, but those are not for general purpose use.

Try it some time. I guarantee the kid will tell you to f*ck off.

SBCL gave me

I might have done it as a kid if challenged and a decent prize was in the offing. Otherwise, you're right. I'd have told him to stuff himself. At least I don't need to offer prizes to my CPU. Sheesh.

I don't have to, Thomas Womack already did in

Terje

Math(s) or arithmetic. Probably the answer is both for (most) children.

Peter

In article , legalize+ snipped-for-privacy@mail.xmission.com (Richard) writes: |>

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

|> >|> >In the latter case FPGAs are unsuited. |> >|> |> >|> I remain unconvinced just because you state it to be so. |> >

|> >In which case, I won't bother to say that Terje is right, because you |> >won't take any notice. |> |> Your arguments are essentially an "appeal to authority", which is why |> I don't find them convincing. If its so trivial to prove the |> assertion, then I don't see why this would be a problem.

No, it's not. Terje, I and others have repeatedly pointed out why that is so. You put some minimal effort into finding out a little, posted incorrect claims on the basis of it, and will neither accept correction nor look more deeply into the issues. The data for both of Terje's statements are fairly easy to find, if you can be bothered.

|> >Why? We are not paid to educate you, and we are not inclined to do |> >so if you don't want to learn. |> |> I didn't ask you to educate me; the assertion was made that FPGAs |> would be horrible for this and I'm interested to know why. ...

Yes, you did. You want an explanation of what you could perfectly well find out for yourself with a bit of effort. Look that up for yourself and, IF you have trouble understanding, THEN ask again.

If you had asked for references in an appropriate fashion in the first place, someone might have helped you.

Regards, Nick Maclaren.

Man, you are one argumentative dude. Thomas Womack posted something useful. The rest of the posts on this just said "it ain't so" without providing *any* data.

So Thomas has given you a fish and Nick is suggesting a fishing rod.

Especially a problem with 260 and a 290 digits. 75,400 single digit multiplies. At one every two seconds (time for the multiply plus some time for the carry), that's 42 hours straight and that's not counting the adds. Good luck getting a kid in today's video game generation to do any task that takes more than ten minutes. The odds of there being no mistakes is vanishingly small. I'd say the odds of absolute peace in the middle east for the next two centuries is higher.

By the way, the answer is:

My intel compatible processor had no problem at all. I didn't even have to install any new tools on my linux box. The lowly 'dc' desk calculator app did it just fine.

I'd like to see you multiply two 100 digit numbers dictated to you. you're not allowed to write them down....

no, it's realistic.

memory is finite.

The usefulness of arbitrary precision math not significant enough.

so do arbirtary precision libraries...

Bye. Jasen

what if x,y,and z, are 100 to 200 times wider than the widest register?

Easy!

In that case you're working with variable length/arbitrary length numbers, in which case unsigned overflow cannot happen. :-)

The code above is a basic building block for such library code.

Terje