Slashdot Mirror

Configure says: checking for __gmpz_init in -lgmpxx... no configure: error: GNU MP not found, download at http://swox.com/gmp

Guess what? That link is a 404.

But with some searching it's possible to find the latest version of GNU MP (http://gmplib.org/), but even after sucessfully building that, you still get the same fucking shit trying to build IHU (I Hate You).

I'm sick to fucking death of that kind of horseshit.

And I'm GNU/Liunx's biggest fan. I've been getting my frustration fix downloading and building this shit since Linux kernel 0.11 in 1991.

But the dumb-fucking-ass fucktards that write some shit and throw it over the wall, and forget about it, piss me the fuck off.

Probably the same squirt who said 25 to 30 year olds were old-timers.

Maybe if you started programming when you were 3, junior.

For the curious...

And don't forget about doing DFTs over finite fields as used by GMP.

struct fraction { public: long long int numerator; long long int denominator; }; // covers anything in that article

There's a reason some people shouldn't be in industrial computing. Problems like this are trivially easy to solve, and have in fact long since been solved by infinite precision math libraries like GMP. There is a common datatype called BCD (binary coded decimal) which handles these problems by just counting 0..9 in each hex digit and then ignoring the other six values, which solves this at arbitrary precision; the first time I saw that was in Paradox in 1988, but I have references to it in books from the late 1960s.

This is a non-story, documenting one author's infamiliarity with basic practices. Nothing to see here. Move along please.

Rational number arithmetic is a more general solution. Any number that can be expressed in decimal or floating-point notation is rational; any rational number can be expressed as (n/d), where n and d are integers. We have "bigints;" unbounded-magnitude integers constrained only by the memory of the computer they are stored on. Rational numeric data types pair two bigints together to give you unbounded magnitude and precision, and have been implemented for decades.

They probably aren't directly supported in your favorite programming language because they are slow to work with when you need very high precision; after each calculation, the rational number needs to be reduced to its lowest terms. This involves factoring, which takes time proportional to the the terms themselves.

Consider the use of integers, floats, or decimals only as an optimization when it has been shown that an application is suffering a serious performance hit because of rational arithmetic, and when you can use a faster data type knowing that your program will perform within accuracy goals.

For 90% of computing problems, monetary calculations included, you shouldn't even have to worry about what numeric type you're using. Your language should assume rationals unless told otherwise. Common Lisp, Scheme, and Nickle do exactly that.

C developers can use GMP. Other developers can use one of many bindings to GMP.

Is GMP similar to that? I used it to approximate the Poisson function for BER calculations. Pretty easy to use.

because we can safely asume that to "count" an atom takes at least one atom, which would then need to be counted, which takes more atoms ad nauseum. No?

No. With 1 bit you can count 2 different things. With 2 bits you can count 4. With 3 bits you can count 8. With 128 bits you can count exactly 340282366920938463463374607431768211456 different things.

because we can safely asume that to "count" an atom takes at least one atom, which would then need to be counted, which takes more atoms ad nauseum. No?

No. With 1 bit you can count 2 different things. With 2 bits you can count 4. With 3 bits you can count 8. With 128 bits you can count exactly 340282366920938463463374607431768211456 different things.

Read about the benefits Intel ascribes to 64-bit software here. "Processors with Intel EM64T support 64-bit capable operating systems from Microsoft, Red Hat and SuSE." And you won't be able to run them.

There are some applications where a 64-bit CPU can perform FOUR TIMES more work in 64-bit mode than 32-bit mode. One of these is big integer multiplication. Check out Is 32 bits really better than 64?": "If we instead would compare an Athlon XP and an Athlon 64, the latter would be almost 4 times faster. Why 4 times and not just 2 times? Because a 64x64=>128 bit integer multiplication actually performs 4 times more work than a 32x32=>64 bit integer multiplication!"

If you want a low power 64-bit CPU consider an AMD Turion based notebook. Check out this article and its conclusions. In particular, "A lot of people see Dothan's 27W TDP & Turion ML's 35W TDP and assume that Dothan is automatically lower power. Intel computes thermal design power as 75% of the maximum load on the chip, while AMD's TDP rating is derived from the absolute worst case power dissipation of the chip. Part of the total system power is also incorporated into AMD's TDP, as the memory controller is located on-chip. Intel's memory controller is built into the chipset and thus draws power not calculated as part of Dothan's TDP. Also while Turion 64 is at idle (800MHz clock speed), it's performance is likely to be higher due to the higher bandwidth data bus. All of these factors contribute to Turion 64 being more power efficient under low load circumstances."

And the -MT Turions have even lower power consumption: AMD Turion 64 specifications.

My next notebook will not be constrainted to only running x86-32 software.

> That's a feature of C then.

Not so. That's the behavior that results from not using a carry bit. Typically, processors perform an operation and stuff the carry into the flags register; the program never looks at the carry flag. C doesn't even have a facility for doing so, so you'd have to dip down to assembler. There really are only about three reasons to use this bit:

1. If it's part of a number larger than a processor register, in an bignum library like gmp.
2. A specialization of #1: some languages (Python) start out with an int4 and replace it with a bignum if it's too large. The same effect but a little more efficient than using bignums everywhere.
3. If your language actually does throw overflow and underflow errors on integers. These languages are fewer than you'd think...maybe Ada does? (If you've seen an overflow or underflow error elsewhere, it's probably from a floating-point operation.)

> > Any modern processor can do an addition or subtraction in a single clock. Yes, carries make it a bit more complex, but that work is done for you by the processor designer.

> We look at ways of getting things done as quick as possible on as many architectures as possible, from the very big (x86, 68k, etc...) to very small (homemade architectures, 6811, etc...).

Even a homemade architecture should do addition or subtraction in a single clock, or it's just not worth using. God, I hope they showed you ways to do that. Here's the obvious, easy one - make a table of the inputs and outputs, make SOP (sum of products) logic to produce the outputs, and apply a logic minimization algorithm (such as Karnaugh diagrams or the Quine-McCluskey method). If it meets your fan-in, fan-out, and gate count constraints, you're good to go. And in two levels of logic; you'll get no faster than that.

There is no known example of a composite number p that slips past all of these tests; I'm confident that nobody will ever find one by accident.

There is no known example of a composite number p that slips past all of these tests; I'm confident that nobody will ever find one by accident.

Yeah, what the other guy said. Also, if you really need arbitrary precisions try GMP.

Just thought I would add something instead of just saying "neener"

I got -15683... but I think my counter rolled over.

You'll need this then, particularly when IBM counter-sue for exemplary damages. ;)

The parent post is insightful. For some operations 64-bit computing can even be four times faster. As GMP developers write in Is 32 bits really better than 64?, ``If we instead would compare an Athlon XP and an Athlon 64, the latter would be almost 4 times faster. Why 4 times and not just 2 times? Because a 64x64=>128 bit integer multiplication actually performs 4 times more work than a 32x32=>64 bit integer multiplication!''

Oh, I don't know. Look at these.

I might also suggest testing the input to make sure it's prime. The library can do that for you IIRC

Hardware floating point is only so accurate - if you need more floating point (or integer) precision, use GNU MP - a library for C with bindings for many other languages too. It came in quite handy when I wrote some cryptography code with very large numbers.

scot lockwood killed my hampster

for the Itanium 2(tm). Just looking at these figures makes my heart flutter.
Why can't Intel make the Itanium 2(tm) available to the rest of us?

Lastly, I am supplying some information to people who know very little on the subject.

I thanked you didn't I?

If you want to write up a CPU Design FAQ for dummies, have at it.

I don't design CPU's, though I have been designing digital devices since the late 80's.

Furthermore, the CISC architecture is designed in a way where more work is theoretically done per instruction.

Careful wording there, impressive. More work per instruction. Well that is the basis of CISC. But whether this is an improvement over RISC is hard to quantify, with individual implementations of both giving differing results that cannot say one is better than the other overall. These CISC instructions that do more work, also require more clock ticks to complete. But then RISC instructions, which usually take only a single clock tick to complete, usually need to be combined to do the same work as a single CISC instruction. The P4 though, does some impressive magic with CISC->RISC processing that blurs the traditional concepts.

But how about work per clock tick, which is what matters if we're talking about the MHz myth...

Here http://www.swox.com/gmp/gmp-speed.html are PowerPC's doing MUCH more work per clock tick than a Pentium 4. Seemingly many times (3.4?) more.

Hell even the old 603e seems to be substantially faster than the P4 per clock tick, in these tests.

BTW, the Itanium 2 would appear to be a rocket!

VCD encoding, G4 doing more per clock tick than an Athlon http://klicman.org/altivec/

I'm not saying a current model G4 is faster than a current model x86 based machine, BTW. But if the PowerPC 970 can get close to the clock rate of the P4 (or then P5), we might see "G5's" running "P5's" into the ground.

PS, I have an old 300MHz G3 iBook, after about 15 years of x86 (currently have P3-500 amongst my currently 16 something PC's). I'm not a zealot of either, but I hold high hopes for the 970.

Gnu MP for mult-precission numbers. They use the fastest known algorithms and hand-optimized asm on most platforms. I prefer to do crypto in Java and use the BigInteger class 'cause I'm lazy.

FYI, Sun's BigInteger.isProbablePrime(int) function is broken... don't use it. I was rather embarassed when a collegue and I emailed some people about a possible bug in the Secure Remote Password protocol, only to discover the problem was a known bug in the JVM... which Sun refuses to fix. I don't know why they won't fix it. My personal implementation of the Miller-Rabin primality test runs faster and correctly identifies the SRP modulus as probably prime. (Look in Applied Cryptography by Schneier for how to code it up.)

The gmp speed chart shows that the Alpha overwhelms the Athlon with its very fast multiplication instruction. Other than that, even the P4 performs faster in other simpler instructions such as moving data around (as shown in lshift and rshift). This chart should be "relatively" unbiased since they have worked pretty hard optimizing the Alpha and Athlon assembly routines.

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. There is no limit to the precision except the ones implied by the available memory in the machine GMP runs on.

Mundie and MSoft have directed the public discussions pretty effectively, they just keep poking at that fanatical GPL nerve; impressive that they've made the GPL the absolute center of discussion, equating GPL and open source. Controversy of the GPL makes it a weak point for open source, by equating the two Mundie/MSoft have assigned to open source all of the restrictions of GPL.

As long as we're stuck on GPL, at least mention some of its variants -- LGPL, special-case GPLs, whatever.

Somebody help me out here, try to think of a commercial product using maybe RTEMS and Microwindows/Nano-X and the GNU MultiPrecision library? Or some other not-necessarily GPL combination of open source libraries that doesn't require derivative software to be all open-source?

A commercial product can use software libraries like these; the developers of such a product comply with the library licenses by publishing changes to the libraries, etc., so forth, to contribute to open source. But the commercial product remains proprietary.

Could do some effective MundieBashing, saying "RTEMS Nano-X GMP LGPL proprietary derivative software," proving the man wrong and derailing his agenda by focusing on open source strengths.

http://www.swox.com/gmp/gmp-speed.html

The Alpha 21264 (aka EV6) pretty much beats the crap out of everything else. It's widely known that the Alpha is far and away the best platform for intensive mathematics.

FWIW, an EV6 (or any alpha, for that matter) can do both a FADD and FMUL in one cycle; a 1GHz Alpha therefore gets 2 GFLOP/s (assuming no cache misses, of course). A lot of the optimizations from generation to generation are for improving branch prediction, cache service, etc, which helps get the real-world numbers closer to the theoretical.
--