Why can Haskell handle very large numbers easily?

问题:

Hugs> 94535^445
1376320882321377050696053887661515621104890164005282153069726424773999801846841903244827702943487982707454966009456016735041878000604143500908532887464920380605164932112687039059526672109818924234920844448231612532570718657160234177285377733830104834041049076609912488237219608445995072867798430614935403219495883835042862802917980856774134757390782052200512932375660858045003581611863121089979673784484701791210379500218604466721285456487387736825167702127154268533859979529612671925052419513844416493584817268143587955662039327860394141299238613042312035808541735213479394437496215520277526351425482512084759462579494878772787079101513841720202004639843443083454387175700954018825292148776647553122504118229978165851660083576570848983047255050145168802863168613110619584686348869690774233051669081248424584219383477237544209892290799448207462345346336076966775224683516220960618177284844330167142846351091001423033864986042919757795382577032341453971393897073354841924116635150129850119992031076354249371062307034564093077675129303383786693131843907104175619570678630497198824622804914508555467550904967368926176118094672479099827962889569753303773699017596074205893197641101210911874606040804983166177455705972192827752532495287749766682029353154226049380290040508900715169403153139668217790502306177709467234413947747673881158973344492079455405942662489751581189327200960698310350121179918845099840977270519116578719881752429190273998774113278822810866144521416958558406602325070095207349450759264393913367193083149679216066539911941983836313340998945139132421885688290888674594474605510238217590823316979504437667252929278291853368754482552573193289277120902144178425726693671235675042499401282016643202758246845332593475338220708351934511933096882598943512036679145593929114103343255708217768511665236173107020739195152050863630870948954052925049746246549772984384435109578859863612603574306739909728739428192798727373799081111333186135697868385292787575475482883660605162944306327057220313320376280182432763977906971557137715710757099478269250731209785404487629107297262798803645379809868663503452656912571816192881412782623078761411808958183665272686617730596943579533808499348879195167683064937591552734375

Why can Haskell calculate such a large number, and other languages, such as Java, cannot (so easily)?

回答1:

Java has the BigInteger class.

It could have built this facility into the language, but (like many languages) it tends to make the primitive features map closely onto things that are supported by the CPU.

Haskell on the other hand emphasizes expressiveness in the style of mathematical notation, where "performance" considerations are largely irrelevant.

回答2:

It's a difference in design philosophy:

• The designers of Haskell wanted to be sure that users would not be surprised by the seemingly arbitrary failure of an integer computation needing more than 32 bits.

• The designers of Java wanted to be sure that users would not be surprised by the seemingly arbitrary performance degradation caused by doing lots of computations over integers needing more than 32 bits.

In each language, you have to do something special to get the other kind of integer.

There's a long, honorable history of languages supporting arbitrarily large integers by default. Two of my favorites are Icon and Smalltalk, which are both over 25 years old.

回答3:

Numeric literals in Haskell are overloaded so that they can represent multiple concrete types (like Int, Integer, Float or even MyOwnNumber).

You can manually chose a specific type by providing type information, like so:

x = 4 :: Int
y = 4 :: Integer
z = 4 :: Float

These three values have different types and operations performed on these will behave differently.

The exact size of an Int is implementation dependent but can be something like 28 bits, this type behaves like a Java primitive int, e.g. it will overflow.

An Integer is a type that can contain arbitrary-precision integers, like the Java BigInteger.

And a Float is like a Java float, using floating point arithmetic.

Just like numeric literals, many operators are also overloaded (using type classes), and can therefor be used with the different types. So the + operator can work with both Ints and Floats.

In your case, since you didn't provide any type information, the interpreter will default to the Integer type. This means that for the ^ operator, it will also choose the Integer instance. Allowing for arbitrary-precision integer calculations.

回答4:

Java has the notion of "Primitive Data Types" (which are the types that the processor supports) and those are different from all other Classes.

In Haskell, Int is a type like all other types, and therefore it was easily made a member of the Num and Integral typeclasses used in (^) ("(^) :: (Num a, Integral b) => a -> b -> a"). Another member of those typeclasses is Integer, which supports integers of all sizes (as long as you have enough memory for their digits).

In Java, you can use many "Big Numbers" libraries, but the operations for them won't use the infix operators you are used to, because those are only for "Primitive Types" in Java.

回答5:

The short and basic answer is that they implement default integers differents. In Java, a standard int is 32 bits. Signed, that gives you a range of −2,147,483,648 to +2,147,483,647.

That said, Java has bignum classes too. If you use those, you'll also gain the ability to use arbitrarily large numbers.

回答6:

As already mentioned, if you have 32 bit words and use the full range you get -2^31 to 2^31-1 using two's complement.

By reserving a few bits of the word, those bits can be used to carry type-information for the value. That is, values "know" their own type at runtime. The remaining bits are used to carry the value's data.

Integer values that fit in these remaining bits can be stored directly in the word. Such integers are typically called 'fixnums'. If they don't fit, then the type bits of the word indicate it is a 'bigint', and the remaining bits are used to store a memory pointer into the heap where the bigint value is stored.

The compiler needs to translate your arithmetic expressions into multiple code paths that cover allowed type combinations for the operands. Example for addition:

• fixnum + fixnum
• bigint + fixnum
• fixnum + bigint
• bigint + bigint

A lot of optimizations in compilers for these languages focus on avoiding overhead for the runtime type-checks needed to make this work. There are often also ways to explicitly tell the compiler that automatic demotion from fixnum to bignum is undesired, and instead one want the overflow behavior of 32bit integers. This can be very important for implementing cryptography algorithms efficiently.

回答7:

It is a matter of how to encode numbers. The traditional way to do this is to encode numbers with a given number of bits, where you cannot have infinite accuracy. Haskell apparently do this with a variable number of bits for a number which is also fine, but usually mean that all math has do be done in software, as hardware acceleration is generally only available for finite accuracy.

回答8:

You can use BigInteger to do the same thing. Haskell is a functional language which is more terse than Java.

One reason we have so many languages is that different languages are better at different tasks as they were designed with different assumptions. Most functional languages are simpler with mathematical functions but tend to struggle with other use cases e.g. haskell is unlikely to be good choice for writing a GUI.