Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
107 lines (68 sloc) 19.1 KB

CMSI 186-03 Programming Laboratory, Spring 2017

Assignment 0403

This assignment asks you to do something that we all know how to do: arithmetic. The wrinkle is, you are asked to implement arithmetic from scratch (“first principles”), and to motivate this, we’ll do arithmetic for something that isn’t available in some programming languages: arbitrarily large integers.

Background Reading

You may refer to the java.math.BigInteger class as an example of an arbitrarily large integer implementation, but for reference, experimentation, and testing only. All submitted code must be written by you.

Automated Feedback Setup

In order to connect your repository to our automated code review and feedback system, once you are up and running please create a GitHub issue requesting this on your repository and mention Ed Seim in it (@SirSeim). Once he has you hooked up, the system will provide feedback on code formatting and quality whenever you commit a new version to GitHub.

You are advancing further in this assignment not only with the program itself but with some best practices surrounding this work:

  • You are now expected to write your own unit tests. A starter suite is provided, but it does not cover all of the specified methods. Follow the pattern from the previous assignments. The automated system will now run your tests and tell you how you fare. When grading, we do have our own suite of tests to ensure proper coverage.

  • You are now expected to indent and format your code more strictly. At this point, you have two full assignments which include some feedback (but no deductions) for needed improvements in formatting your code. For this assignment, deductions will accompany severe issues with code formatting/presentation. Please consult the “Curly-Brace” Languages section of the LMU CS Hacking Guidelines site for details (a Java-specific page has not yet been constructed).

The test suite will still be run automatically whenever you update your work on GitHub; the only difference is that most of the tests will be yours, so their reliability and thoroughness are now up to you.

As always, points will be deducted if issues reported by the automated feedback system here linger in the final submission.

First Principles: Intzilla

Write a class called Intzilla that represents arbitrarily large integers. Instances of this class may have up to Integer.MAXINT digits (once you look it up, you’ll agree that this value is big enough for the label “arbitrarily large”). An API description of this class can be found on the course website. The required methods should be fairly self-explanatory.

Demonstration Programs

To demonstrate the power of your large integer class, write two or more simple applications using this class. A free Exponent example is provided to get you started; this program raises an integer (including negative numbers) to some non-negative integer power (including zero). Assuming that you have implemented Intzilla, you can run Exponent in this way:

$ java Exponent -3428347589 1001
-3428347589 raised to the +1001-th power is -41680414970680884503153567358962294511528007326776370126653341447944002357821496541381657998451021228423345204848045447904151259182505608474136725852786883135423561450825039009781862370612311154138384102621858184095555955545144862070633931970354441933662109332346148919760592885380716951926799689020341981604562493194408337436375569399461744512566354413336671180367088406841754013337017039444579028071741204257838515932491311287216092327002118599606953063384174497212736896785926648869173922876475596267566593560950523894441076339504732752174953887314096414666688119478784391525353347437183282134018640013264267116298508563767514354585919499138438123697578711840925502624306656602498736892218309422595977455491745369258506007494321114718790040721864568399159863780135468530499828988873509368378581066984315950041691802199384351843184958541563273570404258328594534852112250986738932386310888587342096056711187034520799982849881913191336788943346539839176692668607213792039963381611279905228252849439060129771334988660971885032183497977040496640943662885049102473062477619417615294949535114676003269223901330024827329296248398197978498455698667021452876173993924941806516027817410467226990922911030730686077535137587617428402900374534656279498373722426014574135622801390451751426628638178831187399083706685426768621140205916439420089468070914637289595541895736873729727298282752164916782942897483470988933678585773497577979042183401459048733732518714849384621638092699142912457615646098600113584955220750996703559924296540584741202090048784705112319470764873733314298744053533910207719734459388516056633294902343999548980691316186032573018978374001011988199308790736893544029148023349342067722325066828981391526287699451178844957026083618072897068692160344177884630990920865595133365821715947769620459121055168506098020565561001208544025427240565049609769233636151305893210271853620397350120969029472603442707931926238112161245080611255797164208727796861583320575181694156075061106781801055503756436104991150295875709916229691078819403246305544392125882453154984791667636979051521107733175882562954414741221186600856285524920682821374204727986831770062248849602594692526450678369361631037254615302190549017855448216382292451423024977984284095578751867826679969142433932171557447755125013050157231961508407807167253079660859211351406352941188389155292956499131486977155198192480780190479185808658261116245220378259188818108309669375166558277402971383302751583236919478973987502757987070904300236571987625650495781042707400928081759120878499413580721552776616164183526939731067007895259739629216854654577865744473069713337768366974617884816291975755201163767443608765887787567439249133851179549396122842372500097802169972682437217460295899427694059574499978630917544513907403523692727184417254533042431877437886960763544762918015080206684165998137576970828237385456896945404683502200870133026821782052685791722134850833481091616776592081545944892170487713957638396923458422339965629435598008757591387435226855949254316976689855783934889447452705598197459791828732100179586144884196564452427742975028851671194914128358160804489241102450629692624691699338323490102473451196720688706113615059091269167089751637007207821474306448883396704323869200794571112356344776454739418326380459782787509903414436786132956781808007539858142348148338117948394356073299088605849437723610050119603073617564524264722705101157979754201638979852725852704362085901785555947604149284422715420557581878859202807349468616379199933116399289134366553222535559295074320932407966444992005440437352038483252370777089417497897726445529481820702778485082617405168283631818810093636442375668821412912638267365101643956871885102647610494736081433400442866569614204781132497230030210348744776758141294899772407073959200859344623074349885998370764112296771783353647347676373785010695518056145611629570858185370097252630304553670978853134325541031948365108071870618325096914384504778119959501075181053603035647216089917823040841608052249551189430663318099720776256171622693019248737179605502405858334729048018714009423356648634305716906391251106375115478570817895561724819418827100509934863302109136751975261116787717413388937134891088273962260297553594991217423421740585138088050421719871980783911148503204107391607037196872840931137646462758160028141260183047475837086813641842876063751898560984116952646700647348038567282344233859019951750520224871573388411151720652087402276194255892122051367379360501122604361308624625811700359782221647686549210248615346803174991452496341966831581135921275692898244912591103824073810387458006791405336082782125875514369736111923576194544249086226516158273036480061908753197238238136518608473667358204560597011989858601636816584132114213834660188596340504705744417122983036010522520710591537936944031847813926793726709110670125977395872887898980444947448519697415316485503388512697760834785856378780432006844001662891670617388768963743440973482233705543967626568919444080298507788751172064182992188905155364865595499942886706100731506715670318836822969968052818748316652126649469484208075388836991899844802551354986560000826461828271764696137523390183575427722712555472136504527576505806391036866817538555292329954978469589103842988285145625534427782128797914621314371470195045484401935332495766759324619191532607842495815068346548601555135935737789256495201916483521497471911237490307506336008156073206269419415875652482240597238753225880684392545745391514248807749779820197148226177525621975949886711111571223152194135617781974148984680236724334191730059447403806146981007471160265429112179258653845018186176433600726018540953823273143526798877321769702008988974538816745385021921201506273345461826576853116290158017852004596944843415625366764917916219475122908807179950881717391473069952951948950620748784869895352742004836590587438457231988651094535908953926361787147817783088022149813021630910812471430208899851284539518297800885146539957314519162418270469761715073607316472621280996809521764072144815605648938873047653884286297747805314947875850476599901918167372058987242052574575636875403535652689090699043289646074668542830099658105560798520017020365519226579948489532549004898485872979583201649998894079736851924614827537289150706359886112691033738265255476092036662816858766525725400885914046632761801687280055920215917040224338443948563255153935524552661586868675571080339932104829830918892163447430748452294190460048367686626137191200670658093926805504695412799097802680187455021209483194444184962150737638848777657252034562393162971912604262980122364911730938105583366593198728646921010428778689583275351063739488855293063373572456894217278201001809143540324449956910879906932327017795887354492546482743228479991435060709729621708105093401189096003459571561909753051631233460022492950972977090385748731503956705022889924569985355601529365438491113244927072063188441723032746817189881190015904099906030479757111908698547568807377880726406518112150411170106210053599864229442980490609746548412905440346838189142419885564671376440508457627661967504567263755796217236519993801325812950325412343312395166216618508975629351955779378110397697466251920970771256402526848284647771009636302180928626608811485848809435280332029489521908252828038741294408293034622127189789195693017456760242203147377057675347455657609267663637361796009497964049491090020631797967681850379335166148474165925844644148731411472091182083966346146497601733719434794579064070154959007254087107180128725116303801327456552879670992339143557814194264992775745786308873555030376217053955877623841458876599678724905985602124979805328591455554843766207917486239172054199584817479013594642756935813879208869062201775293707981098957626524519511715730813540516293046050531272986304595274357541346940770037982637814500780716481904594323105703391746604339392719751815487615146515534631620206285602743361898910098985092006132153741649208080044265771833602268904265950200199259555202519423750195488630671938531698938514669137702984618546928153031682061948602178789313739761899432627414485354560844654902828188179906457632754427232175964819312325984788378299597563450036601429252405907920067482720088437144492075837699646397100470731148157319215436549850877621107355626966045474406782328399528445610937041208633010755656438343944421965035654123120251087317637000047912780746379544654399939140412774430639317760419971672713082526796231638962887756113344943287559354980325839261823590095912843144699924927608932981578403351349322408549739409425226904818557264127887768891941199012766167118909190639307341654074883313637636618534079927581645385874485551194831122775310411565414659519328187219342222705583047528530942013395795132102249731988608428781455253026900175866052021852815048941277158114096053351501620207931670348805675933639630615251350716159624232828980285071220771539014532210927849497785822321266977375874321705112056436508360609489504707338590276444002306467688791232633739590618961301520222794254425693075607062202196475034400986093324525496072232946975868834362347070696088762535790018489493607090740214129884847307690114236999244071048259127744205154803496236906068499388346972852794708821151674466409611563856670217195812898016636126855991599160134645712708632428527106899411883989473798310440862270518116023021970851516650630042964680714833959087933246706844166186478039534820936849335297286957680717311128622690375059914825039401386061488341656801975680179524146765758668940101927015848263904409095159093318145831854012054147192723468530925014013513522547596662887589.

Some ideas for demonstration programs include:

  • A Factorial class that calculates the factorial of any non-negative integer.

  • A Fibonacci class that takes a natural number n and calculates the n-th number in the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...).

  • A DataStorage class that takes a number and a data unit (e.g., kilobyte, megabyte, gigabyte, terabyte, petabyte, yottabyte, etc.) then displays the number of bytes represented by that value. To keep it interesting, use binary rather than decimal multiples; prefixes and corresponding powers of 2 can be found on the web.

  • A MarketCapitalization class that takes a stock price and number of shares for some company then displays the market capitalization of that company. (look up the stock information of a favorite company to see some examples—for simplicity, assume that amounts are given in cents [e.g., a company with a stock price of $122.34 would be entered as 12234])

Design Notes

  • You are free to decide on the internal representation of your arbitrarily large integers as well as your implementations for their arithmetic operations. What matters is that you produce a class that works correctly, and that you implement these operations from scratch. That said, you might wonder whether a non-decimal internal representation, such as binary, might be worth exploring. If this is a consideration, you’ll want to convert decimal strings to binary and vice versa. The last section of this writeup includes notes on doing that.

  • As always, write out compilable stubs for the code first.

  • A starter test suite has been provided, but is by no means complete. However, to get started, you can implement the methods for which tests have already been written.

  • Beyond the starter test suite, write new tests first and then implement the tested methods—much the same way that previous assignments provided the tests before you filled out your code’s method stubs.

  • For methods that are not finished by the due date, throw an UnsupportedOperationException.

  • Note from the above bullet that this assignment is known to be highly challenging. Fortunately, arithmetic is something that we largely know how to do by hand; the trick here is figuring out how to express these activities in Java.

  • Certain approaches to arithmetic operations are easier to program and run more efficiently than others—pay attention in class for some possible algorithm alternatives.

  • Although these integers are created and displayed as decimal numbers, there is nothing stopping you from representing them internally with a different base (e.g., binary). Consider this alternative when deciding on a representation. We are striving solely for correctness here, and are not worried about performance or efficiency. (though the arithmetic should not take a prohibitively long time either)

Decimal string to binary, and back

Representing large integers in binary (base 2) makes some arithmetic algorithms easier to implement, in exchange for the need to convert a decimal string into binary in the constructor, then to convert binary to a decimal string in toString.

Note also that even if you don’t go binary, the description of “specialized” division and multiplication by 2 (halving and doubling) may be of use if you choose to implement Russian peasant multiplication.

Decimal String to Binary

The key to this is to have a specialized divideByTwo helper method, whose sole purpose is to cut a string that contains decimal digits in half, ignoring remainders. Because we are ignoring remainders, every digit you process can be subtracted by 1 if it is odd—e.g., 1 becomes 0, 7 becomes 6, etc.

Note then that all digits have two possible halves: e.g., 0 comes either from 0 + 0 or 5 + 5; 6 comes either from 3 + 3 or 8 + 8. How do you tell which one? Well, the next larger digit will tell you: if the next larger digit is odd, then the original half digit is the higher version (e.g., for 58, note how 5 is odd, and therefore you get 9 for the lowest digit). Further, if the next larger digit is odd, when you move on to that digit, you subtract it by 1. Looking at 58 again, you would see the 8 then write 9 because 5 is odd. 5 – 1 gives you 4. Divide that by 2 and you get 2. Thus 58 / 2 = 29.

That is basically the “specialized” division by 2. Now that you have that, you can convert to binary. The algorithm goes this way: if the smallest digit is odd, write a 1 and otherwise write 0. Then divide the number by 2. Repeat until you are out of digits.

So for example, to convert "312" to binary, you would go:

312 -> even -> "0" -> divide by 2 -> 156
156 -> even -> "00" -> divide by 2 -> 78
 78 -> even -> "000" -> divide by 2 -> 39
 39 -> odd -> "1000" -> divide by 2 -> 19
 19 -> odd -> "11000" -> divide by 2 -> 9
  9 -> odd -> "111000" -> divide by 2 -> 4
  4 -> even -> "0111000" -> divide by 2 -> 2
  2 -> even -> "00111000" -> divide by 2 -> 1
  1 -> odd -> "100111000" -> divide by 2 -> 0 -> done

Notice how 100111000 = 256 + 32 + 16 + 8 = 312.

Binary to Decimal String

This approach is known in LMU as “Dorin’s Way” because, well, it’s Dr. Dorin’s way of doing this conversion. It is interesting because it processes bits from left to right (i.e., largest magnitude first).

For this, you will need a doubleDecimalString helper. This is a special-case addition of a decimal number to itself. You will also need an addOne helper, which adds 1 to the decimal representation. That is also pretty straightforward—but do watch for the 9 case!

Given that, start with an initial value of 0. While there are still bits to read, from largest to smallest: Double the current value. Read the current bit. If it is 1, add 1 to the current value. Move to the next bit.

That’s it, actually. So let’s convert our binary 100111000 back to 312:

start with "0"
double "0" is "0" -> leftmost bit is 1 -> add 1 -> "1"
double "1" is "2" -> next bit is 0
double "2" is "4" -> next bit is 0
double "4" is "8" -> next bit is 1 -> add 1 -> "9"
double "9" is "18" -> next bit is 1 -> add 1 -> "19"
double "19" is "38" -> next bit is 1 -> add 1 -> "39"
double "39" is "78" -> next bit is 0
double "78" is "156" -> next bit is 0
double "156" is "312" -> next bit is 0 -> done

And that is how we get "312" back from binary 100111000.

Try it with other numbers…it works every time. Dorin’s Way is faithful and true 😎