27
Hugs> 94535^445
1376320882321377050696053887661515621104890164005282153069726424773999801846841903244827702943487982707454966009456016735041878000604143500908532887464920380605164932112687039059526672109818924234920844448231612532570718657160234177285377733830104834041049076609912488237219608445995072867798430614935403219495883835042862802917980856774134757390782052200512932375660858045003581611863121089979673784484701791210379500218604466721285456487387736825167702127154268533859979529612671925052419513844416493584817268143587955662039327860394141299238613042312035808541735213479394437496215520277526351425482512084759462579494878772787079101513841720202004639843443083454387175700954018825292148776647553122504118229978165851660083576570848983047255050145168802863168613110619584686348869690774233051669081248424584219383477237544209892290799448207462345346336076966775224683516220960618177284844330167142846351091001423033864986042919757795382577032341453971393897073354841924116635150129850119992031076354249371062307034564093077675129303383786693131843907104175619570678630497198824622804914508555467550904967368926176118094672479099827962889569753303773699017596074205893197641101210911874606040804983166177455705972192827752532495287749766682029353154226049380290040508900715169403153139668217790502306177709467234413947747673881158973344492079455405942662489751581189327200960698310350121179918845099840977270519116578719881752429190273998774113278822810866144521416958558406602325070095207349450759264393913367193083149679216066539911941983836313340998945139132421885688290888674594474605510238217590823316979504437667252929278291853368754482552573193289277120902144178425726693671235675042499401282016643202758246845332593475338220708351934511933096882598943512036679145593929114103343255708217768511665236173107020739195152050863630870948954052925049746246549772984384435109578859863612603574306739909728739428192798727373799081111333186135697868385292787575475482883660605162944306327057220313320376280182432763977906971557137715710757099478269250731209785404487629107297262798803645379809868663503452656912571816192881412782623078761411808958183665272686617730596943579533808499348879195167683064937591552734375

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

8 Answers 8

46

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.

2
  • 10
    Although "something special" in Haskell is a bit easier: It just means using, eg, Int32 as your type whereas in Java, it's my understanding that the lack of operator overloading will force you to have to say things like x.add(y) or x.multiply(y)
    – Jason C
    Jul 28, 2009 at 19:01
  • 1
    Yeah I think "something special" is very unfair to Haskell. You can use a bounded int in Haskell with the same amount of code as a bounded int in Java. int x = 5 vs x = 5 :: Int.
    – semicolon
    Mar 20, 2017 at 19:35
28

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.

3
  • 31
    Just to be clear, though: Haskell developers don't in general consider performance considerations to be irrelevant.
    – amindfv
    Mar 26, 2012 at 18:36
  • I agree - I put quotes around "performance" because I support Haskell's approach. Mar 27, 2012 at 8:17
  • 1
    In real-life Haskell code, Int is used. Integer is only used when you would use BigInteger in Java too. So there’s actually no practical difference, except that in Haskell, Integer is the default type if you don’t specify a type. (Since it’s [correctly] assumed not to be production code anyway if no types are specified.)
    – anon
    Nov 21, 2013 at 9:58
13

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.

6

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.

2
  • 1
    See if I understand this correctly. So the ^ operator in Haskell is not directly bound to a specific type, but to a "category" (or two such categories, it seems) of types which in some sense behave alike? Does Haskell then choose which type to give an expression at runtime, but always within the same such category? As in the poster's example, the result of 94535^445 needs an Integer type to be represented, but the result of 3^5 can do with an Int to be represented.
    – harms
    Jul 26, 2009 at 12:23
  • 4
    @harms: Haskell does type inference and type checking at compile time. In this case, since no type information is provided, it will default to Integer (which is like a Java BigNumber). However, you could manually add type information to say the numbers are Int (like Java primitive int), in that case the result of the ^ operation will simply overflow and produce an incorrect Int result. Jul 26, 2009 at 13:03
3

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.

1

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.

2
  • there isn't necessarily any runtime overhead with polymorphism, and take Haskell as an example for that. also, I don't see how the whole reserved bits part is relevant to this question, as I don't think neither Java nor Haskell use that.
    – yairchu
    Jul 28, 2009 at 7:15
  • True, there is not any runtime overhead if it can be optimized away. Haskell (at least GHC) does automatic promotion of fixnums to bigintegers at overflow (for the Integer type). That java doesnt just explain why the primitive int or Integer overflow, requiring the use of bigint and taking the costs even if the value would fit in the fixnum range.
    – Christian
    Jul 28, 2009 at 9:32
0

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.

3
  • 1
    I would rather guess that Haskell provides smooth range checking and number conversion, just like Lisp. As long as your numbers stay inside the fixnum range, calculations are done normally and directly on the machine, but overflow is detected and eliminated by conversion to bignum.
    – Svante
    Jul 26, 2009 at 12:21
  • 1
    @Svante: no, that is completely not true. Haskell has no automatic conversions between any types nor does it have range checking of Ints. it is completely an issue of ambiguous types. in Haskell integer literals can be typed to any type that instances Num. here the type is ambiguous. by default, Haskell defaults to Integer, as explained here: haskell.org/onlinereport/decls.html#default-decls
    – newacct
    Jul 26, 2009 at 18:03
  • 1
    @newacct: While the Haskell Report defines the way Integers behave, that doesn't mean they can't be implemented as fixnums and bignums. Whether there is a Haskell implementation that actually does this, I don't know. Jul 27, 2009 at 0:01
0

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.

1
  • 1
    with ghcjs its now a great choice! Nov 30, 2016 at 19:40

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.