DC−AnInteractiveDeskCalculator RobertMorris LorindaCherry ABSTRACT DCisaninteractivedeskcalculatorprogramimplementedontheUNIX◯r time-sharingsystemtodoarbitrary-precisionintegerarithmetic.Ithasprovision formanipulatingscaledfixed-pointnumbersandforinputandoutputinbases otherthandecimal. Thesizeofnumbersthatcanbemanipulatedislimitedonlybyavailable corestorage.OntypicalimplementationsofUNIX,thesizeofnumbersthatcan behandledvariesfromseveralhundreddigitsonthesmallestsystemstoseveral thousandonthelargest. 6April1993 DC−AnInteractiveDeskCalculator RobertMorris LorindaCherry DCisanarbitraryprecisionarithmeticpackageimplementedontheUNIXtime-sharingsys-temintheformofaninteractivedeskcalculator.Itworkslikeastackingcalculatorusingreverse Polishnotation.OrdinarilyDCoperatesondecimalintegers,butonemayspecifyaninputbase, outputbase,andanumberoffractionaldigitstobemaintained. AlanguagecalledBC[1]hasbeendevelopedwhichacceptsprogramswritteninthefamiliar styleofhigher-levelprogramminglanguagesandcompilesoutputwhichisinterpretedbyDC. Someofthecommandsdescribedbelowweredesignedforthecompilerinterfaceandarenoteasy forahumanusertomanipulate. NumbersthataretypedintoDCareputonapush-downstack.DCcommandsworkby takingthetopnumberortwooffthestack,performingthedesiredoperation,andpushingthe resultonthestack.Ifanargumentisgiven,inputistakenfromthatfileuntilitsend,thenfrom thestandardinput. SYNOPTICDESCRIPTION HerewedescribetheDCcommandsthatareintendedforusebypeople.Theadditional commandsthatareintendedtobeinvokedbycompiledoutputaredescribedinthedetailed description. Anynumberofcommandsarepermittedonaline.Blanksandnew-linecharactersare ignoredexceptwithinnumbersandinplaceswherearegisternameisexpected. Thefollowingconstructionsarerecognized: number Thevalueofthenumberispushedontothemainstack.Anumberisanunbrokenstringof thedigits0-9andthecapitallettersA−Fwhicharetreatedasdigitswithvalues10−15 respectively.Thenumbermaybeprecededbyanunderscoretoinputanegativenumber. Numbersmaycontaindecimalpoints. +−*%ˆ Thetoptwovaluesonthestackareadded(+),subtracted(−),multiplied(*),divided(/), remaindered(%),orexponentiated(ˆ ).Thetwoentriesarepoppedoffthestack;theresult ispushedonthestackintheirplace.Theresultofadivisionisanintegertruncatedtoward zero.Seethedetaileddescriptionbelowforthetreatmentofnumberswithdecimalpoints. Anexponentmustnothaveanydigitsafterthedecimalpoint. sx Thetopofthemainstackispoppedandstoredintoaregisternamedx,wherexmaybeany character.Ifthesiscapitalized,xistreatedasastackandthevalueispushedontoit. Anycharacter,evenblankornew-line,isavalidregistername.

-2-lx Thevalueinregisterxispushedontothestack.Theregisterxisnotaltered.Ifthelis capitalized,registerxistreatedasastackanditstopvalueispoppedontothemainstack. Allregistersstartwithemptyvaluewhichistreatedasazerobythecommandlandistreatedas anerrorbythecommandL. d Thetopvalueonthestackisduplicated. p Thetopvalueonthestackisprinted.Thetopvalueremainsunchanged. f Allvaluesonthestackandinregistersareprinted. x treatsthetopelementofthestackasacharacterstring,removesitfromthestack,andexecutesitasastringofDCcommands. [...] putsthebracketedcharacterstringontothetopofthestack. q exitstheprogram.Ifexecutingastring,therecursionlevelispoppedbytwo.Ifqiscapitalized,thetopvalueonthestackispoppedandthestringexecutionlevelispoppedby thatvalue. <x>x=x!<x!>x!=x Thetoptwoelementsofthestackarepoppedandcompared.Registerxisexecutedifthey obeythestatedrelation.Exclamationpointisnegation. v replacesthetopelementonthestackbyitssquareroot.Thesquarerootofanintegeris truncatedtoaninteger.Forthetreatmentofnumberswithdecimalpoints,seethedetailed descriptionbelow. ! interpretstherestofthelineasaUNIXcommand.ControlreturnstoDCwhentheUNIX commandterminates. c Allvaluesonthestackarepopped;thestackbecomesempty. i Thetopvalueonthestackispoppedandusedasthenumberradixforfurtherinput.Ifiis capitalized,thevalueoftheinputbaseispushedontothestack.Nomechanismhasbeen providedfortheinputofarbitrarynumbersinbaseslessthan1orgreaterthan16.

-3-o Thetopvalueonthestackispoppedandusedasthenumberradixforfurtheroutput.Ifo iscapitalized,thevalueoftheoutputbaseispushedontothestack. k Thetopofthestackispopped,andthatvalueisusedasascalefactorthatinfluencesthe numberofdecimalplacesthataremaintainedduringmultiplication,division,andexponentiation.Thescalefactormustbegreaterthanorequaltozeroandlessthan100.Ifkiscapitalized,thevalueofthescalefactorispushedontothestack. z Thevalueofthestacklevelispushedontothestack. ? Alineofinputistakenfromtheinputsource(usuallytheconsole)andexecuted. DETAILEDDESCRIPTION InternalRepresentationofNumbers Numbersarestoredinternallyusingadynamicstorageallocator.Numbersarekeptinthe formofastringofdigitstothebase100storedonedigitperbyte(centennialdigits).Thestring isstoredwiththelow-orderdigitatthebeginningofthestring.Forexample,therepresentation of157is57,1.Afteranyarithmeticoperationonanumber,careistakenthatalldigitsareinthe range0−99andthatthenumberhasnoleadingzeros.Thenumberzeroisrepresentedbythe emptystring. Negativenumbersarerepresentedinthe100’scomplementnotation,whichisanalogousto two’scomplementnotationforbinarynumbers.Thehighorderdigitofanegativenumberis always−1andallotherdigitsareintherange0−99.Thedigitprecedingthehighorder−1digit isnevera99.Therepresentationof−157is43,98,−1.Weshallcallthisthecanonicalformofa number.Theadvantageofthiskindofrepresentationofnegativenumbersiseaseofaddition. Whenadditionisperformeddigitbydigit,theresultisformallycorrect.Theresultneedonlybe modified,ifnecessary,toputitintocanonicalform. Becausethelargestvaliddigitis99andthebytecanholdnumberstwicethatlarge,additioncanbecarriedoutandthehandlingofcarriesdonelaterwhenthatisconvenient,asitsometimesis. Anadditionalbyteisstoredwitheachnumberbeyondthehighorderdigittoindicatethe numberofassumeddecimaldigitsafterthedecimalpoint.Therepresentationof.001is1,3where thescalehasbeenitalicizedtoemphasizethefactthatitisnotthehighorderdigit.Thevalueof thisextrabyteiscalledthescalefactorofthenumber. TheAllocator DCusesadynamicstringstorageallocatorforallofitsinternalstorage.Allreadingand writingofnumbersinternallyisdonethroughtheallocator.Associatedwitheachstringinthe allocatorisafour-wordheadercontainingpointerstothebeginningofthestring,theendofthe string,thenextplacetowrite,andthenextplacetoread.Communicationbetweentheallocator andDCisdoneviapointerstotheseheaders. Theallocatorinitiallyhasonelargestringonalistoffreestrings.Allheadersexceptthe onepointingtothisstringareonalistoffreeheaders.Requestsforstringsaremadebysize. Thesizeofthestringactuallysuppliedisthenexthigherpowerof2.Whenarequestforastring ismade,theallocatorfirstchecksthefreelisttoseeifthereisastringofthedesiredsize.Ifnone isfound,theallocatorfindsthenextlargerfreestringandsplitsitrepeatedlyuntilithasastring oftherightsize.Left-overstringsareputonthefreelist.Iftherearenolargerstrings,the -4-allocatortriestocoalescesmallerfreestringsintolargerones.Sinceallstringsaretheresultof splittinglargestrings,eachstringhasaneighborthatisnexttoitincoreand,iffree,canbecombinedwithittomakeastringtwiceaslong.Thisisanimplementationofthe‘buddysystem’of allocationdescribedin[2]. Failingtofindastringoftheproperlengthaftercoalescing,theallocatorasksthesystem formorespace.Theamountofspaceonthesystemistheonlylimitationonthesizeandnumber ofstringsinDC.Ifatanytimeintheprocessoftryingtoallocateastring,theallocatorrunsout ofheaders,italsoasksthesystemformorespace. Thereareroutinesintheallocatorforreading,writing,copying,rewinding,forward-spacing, andbackspacingstrings.Allstringmanipulationisdoneusingtheseroutines. Thereadingandwritingroutinesincrementthereadpointerorwritepointersothatthe charactersofastringarereadorwritteninsuccessionbyaseriesofreadorwritecalls.Thewrite pointerisinterpretedastheendoftheinformation-containingportionofastringandacallto readbeyondthatpointreturnsanend-of-stringindication.Anattempttowritebeyondtheend ofastringcausestheallocatortoallocatealargerspaceandthencopytheoldstringintothe largerblock. InternalArithmetic Allarithmeticoperationsaredoneonintegers.Theoperands(oroperand)neededforthe operationarepoppedfromthemainstackandtheirscalefactorsstrippedoff.Zerosareaddedor digitsremovedasnecessarytogetaproperlyscaledresultfromtheinternalarithmeticroutine. Forexample,ifthescaleoftheoperandsisdifferentanddecimalalignmentisrequired,asitisfor addition,zerosareappendedtotheoperandwiththesmallerscale.Afterperformingtherequired arithmeticoperation,theproperscalefactorisappendedtotheendofthenumberbeforeitis pushedonthestack. Aregistercalledscaleplaysapartintheresultsofmostarithmeticoperations.scaleisthe boundonthenumberofdecimalplacesretainedinarithmeticcomputations.scalemaybesetto thenumberonthetopofthestacktruncatedtoanintegerwiththekcommand.Kmaybeused topushthevalueofscaleonthestack.scalemustbegreaterthanorequalto0andlessthan 100.Thedescriptionsoftheindividualarithmeticoperationswillincludetheexacteffectofscale onthecomputations. AdditionandSubtraction Thescalesofthetwonumbersarecomparedandtrailingzerosaresuppliedtothenumber withthelowerscaletogivebothnumbersthesamescale.Thenumberwiththesmallerscaleis multipliedby10ifthedifferenceofthescalesisodd.Thescaleoftheresultisthensettothe largerofthescalesofthetwooperands. Subtractionisperformedbynegatingthenumbertobesubtractedandproceedingasin addition. Finally,theadditionisperformeddigitbydigitfromtheloworderendofthenumber.The carriesarepropagatedintheusualway.Theresultingnumberisbroughtintocanonicalform, whichmayrequirestrippingofleadingzeros,orfornegativenumbersreplacingthehigh-order configuration99,−1bythedigit−1.Inanycase,digitswhicharenotintherange0−99mustbe broughtintothatrange,propagatinganycarriesorborrowsthatresult. Multiplication Thescalesareremovedfromthetwooperandsandsaved.Theoperandsarebothmadepositive.Thenmultiplicationisperformedinadigitbydigitmannerthatexactlymimicsthehand methodofmultiplying.Thefirstnumberismultipliedbyeachdigitofthesecondnumber,beginningwithitsloworderdigit.Theintermediateproductsareaccumulatedintoapartialsum whichbecomesthefinalproduct.Theproductisputintothecanonicalformanditssigniscomputedfromthesignsoftheoriginaloperands.

-5-Thescaleoftheresultissetequaltothesumofthescalesofthetwooperands.Ifthat scaleislargerthantheinternalregisterscaleandalsolargerthanbothofthescalesofthetwo operands,thenthescaleoftheresultissetequaltothelargestofthesethreelastquantities. Division Thescalesareremovedfromthetwooperands.Zerosareappendedordigitsremovedfrom thedividendtomakethescaleoftheresultoftheintegerdivisionequaltotheinternalquantity scale.Thesignsareremovedandsaved. Divisionisperformedmuchasitwouldbedonebyhand.Thedifferenceofthelengthsof thetwonumbersiscomputed.Ifthedivisorislongerthanthedividend,zeroisreturned.Otherwisethetopdigitofthedivisorisdividedintothetoptwodigitsofthedividend.Theresultis usedasthefirst(high-order)digitofthequotient.Itmayturnoutbeoneunittoolow,butifit is,thenexttrialquotientwillbelargerthan99andthiswillbeadjustedattheendoftheprocess.Thetrialdigitismultipliedbythedivisorandtheresultsubtractedfromthedividendand theprocessisrepeatedtogetadditionalquotientdigitsuntiltheremainingdividendissmaller thanthedivisor.Attheend,thedigitsofthequotientareputintothecanonicalform,with propagationofcarryasneeded.Thesignissetfromthesignoftheoperands. Remainder Thedivisionroutineiscalledanddivisionisperformedexactlyasdescribed.Thequantity returnedistheremainsofthedividendattheendofthedivideprocess.Sincedivisiontruncates towardzero,remaindershavethesamesignasthedividend.Thescaleoftheremainderissetto themaximumofthescaleofthedividendandthescaleofthequotientplusthescaleofthedivisor. SquareRoot Thescaleisstrippedfromtheoperand.Zerosareaddedifnecessarytomaketheinteger resulthaveascalethatisthelargeroftheinternalquantityscaleandthescaleoftheoperand. Themethodusedtocomputesqrt(y)isNewton’smethodwithsuccessiveapproximationsby therule xn+1=12(xn+yxn) Theinitialguessisfoundbytakingtheintegersquarerootofthetoptwodigits. Exponentiation Onlyexponentswithzeroscalefactorarehandled.Iftheexponentiszero,thentheresultis 1.Iftheexponentisnegative,thenitismadepositiveandthebaseisdividedintoone.The scaleofthebaseisremoved. Theintegerexponentisviewedasabinarynumber.Thebaseisrepeatedlysquaredandthe resultisobtainedasaproductofthosepowersofthebasethatcorrespondtothepositionsofthe one-bitsinthebinaryrepresentationoftheexponent.Enoughdigitsoftheresultareremovedto makethescaleoftheresultthesameasiftheindicatedmultiplicationhadbeenperformed. InputConversionandBase Numbersareconvertedtotheinternalrepresentationastheyarereadin.Thescalestored withanumberissimplythenumberoffractionaldigitsinput.Negativenumbersareindicatedby precedingthenumberwitha.ThehexadecimaldigitsA−Fcorrespondtothenumbers10−15 regardlessofinputbase.Theicommandcanbeusedtochangethebaseoftheinputnumbers. Thiscommandpopsthestack,truncatestheresultingnumbertoaninteger,andusesitasthe inputbaseforallfurtherinput.Theinputbaseisinitializedto10butmay,forexamplebe changedto8or16todooctalorhexadecimaltodecimalconversions.ThecommandIwillpush -6-thevalueoftheinputbaseonthestack. OutputCommands Thecommandpcausesthetopofthestacktobeprinted.Itdoesnotremovethetopofthe stack.Allofthestackandinternalregisterscanbeoutputbytypingthecommandf.Theo commandcanbeusedtochangetheoutputbase.Thiscommandusesthetopofthestack,truncatedtoanintegerasthebaseforallfurtheroutput.Theoutputbaseininitializedto10.Itwill workcorrectlyforanybase.ThecommandOpushesthevalueoftheoutputbaseonthestack. OutputFormatandBase Theinputandoutputbasesonlyaffecttheinterpretationofnumbersoninputandoutput; theyhavenoeffectonarithmeticcomputations.Largenumbersareoutputwith70charactersper line;a\indicatesacontinuedline.Allchoicesofinputandoutputbasesworkcorrectly,although notallareuseful.Aparticularlyusefuloutputbaseis100000,whichhastheeffectofgrouping digitsinfives.Basesof8and16canbeusedfordecimal-octalordecimal-hexadecimalconver-sions. InternalRegisters Numbersorstringsmaybestoredininternalregistersorloadedonthestackfromregisters withthecommandssandl.Thecommandsxpopsthetopofthestackandstorestheresultin registerx.xcanbeanycharacter.lxputsthecontentsofregisterxonthetopofthestack.The lcommandhasnoeffectonthecontentsofregisterx.Thescommand,however,isdestructive. StackCommands Thecommandcclearsthestack.Thecommanddpushesaduplicateofthenumberonthe topofthestackonthestack.Thecommandzpushesthestacksizeonthestack.Thecommand Xreplacesthenumberonthetopofthestackwithitsscalefactor.ThecommandZreplacesthe topofthestackwithitslength. SubroutineDefinitionsandCalls Enclosingastringin[]pushestheasciistringonthestack.Theqcommandquitsorinexecutingastring,popstherecursionlevelsbytwo. InternalRegisters−ProgrammingDC Theloadandstorecommandstogetherwith[]tostorestrings,xtoexecuteandthetesting commands‘<’,‘>’,‘=’,‘!<’,‘!>’,‘!=’canbeusedtoprogramDC.Thexcommandassumesthe topofthestackisanstringofDCcommandsandexecutesit.Thetestingcommandscompare thetoptwoelementsonthestackandiftherelationholds,executetheregisterthatfollowsthe relation.Forexample,toprintthenumbers0-9, [lip1+sili10>a]sa 0silax Push-DownRegistersandArrays Thesecommandsweredesignedforusedbyacompiler,notbypeople.Theyinvolvepushdownregistersandarrays.Inadditiontothestackthatcommandsworkon,DCcanbethought ofashavingindividualstacksforeachregister.Theseregistersareoperatedonbythecommands SandL.Sxpushesthetopvalueofthemainstackontothestackfortheregisterx.Lxpopsthe stackforregisterxandputstheresultonthemainstack.Thecommandssandlalsoworkon registersbutnotaspush-downstacks.ldoesn’teffectthetopoftheregisterstack,andsdestroys whatwastherebefore.

-7-Thecommandstoworkonarraysare:and;.:xpopsthestackandusesthisvalueasan indexintothearrayx.Thenextelementonthestackisstoredatthisindexinx.Anindexmust begreaterthanorequalto0andlessthan2048.;xisthecommandtoloadthemainstackfrom thearrayx.Thevalueonthetopofthestackistheindexintothearrayxofthevaluetobe loaded. MiscellaneousCommands Thecommand!interpretstherestofthelineasaUNIX commandandpassesittoUNIXtoexecute.OneothercompilercommandisQ.Thiscommand usesthetopofthestackasthenumberoflevelsofrecursiontoskip. DESIGNCHOICES Therealreasonfortheuseofadynamicstorageallocatorwasthatageneralpurposeprogramcouldbe(andinfacthasbeen)usedforavarietyofothertasks.Theallocatorhassome valueforinputandforcompiling(i.e.thebracket[...]commands)whereitcannotbeknownin advancehowlongastringwillbe.Theresultwasthatatamodestcostinexecutiontime,all considerationsofstringallocationandsizesofstringswereremovedfromtheremainderofthe programanddebuggingwasmadeeasier.Theallocationmethodusedwastesapproximately25% ofavailablespace. Thechoiceof100asabaseforinternalarithmeticseeminglyhasnocompellingadvantage. Yetthebasecannotexceed127becauseofhardwarelimitationsandatthecostof5%inspace, debuggingwasmadeagreatdealeasieranddecimaloutputwasmademuchfaster. Thereasonforastack-typearithmeticdesignwastopermitallDCcommandsfromaddition tosubroutineexecutiontobeimplementedinessentiallythesameway.Theresultwasaconsiderabledegreeoflogicalseparationofthefinalprogramintomoduleswithverylittlecommunicationbetweenmodules. Therationaleforthelackofinteractionbetweenthescaleandthebaseswastoprovidean understandablemeansofproceedingafterachangeofbaseorscalewhennumbershadalready beenentered.Anearlierimplementationwhichhadglobalnotionsofscaleandbasedidnotwork outwell.Ifthevalueofscaleweretobeinterpretedinthecurrentinputoroutputbase,thena changeofbaseorscaleinthemidstofacomputationwouldcausegreatconfusionintheinterpretationoftheresults.Thecurrentschemehastheadvantagethatthevalueoftheinputandoutputbasesareonlyusedforinputandoutput,respectively,andtheyareignoredinallotheroperations.Thevalueofscaleisnotusedforanyessentialpurposebyanypartoftheprogramandit isusedonlytopreventthenumberofdecimalplacesresultingfromthearithmeticoperationsfrom growingbeyondallbounds. Thedesignrationaleforthechoicesforthescalesoftheresultsofarithmeticwerethatinno caseshouldanysignificantdigitsbethrownawayif,onappearances,theuseractuallywanted them.Thus,iftheuserwantstoaddthenumbers1.5and3.517,itseemedreasonabletogivehim theresult5.017withoutrequiringhimtounnecessarilyspecifyhisratherobviousrequirementsfor precision. Ontheotherhand,multiplicationandexponentiationproduceresultswithmanymoredigits thantheiroperandsanditseemedreasonabletogiveasaminimumthenumberofdecimalplaces intheoperandsbutnottogivemorethanthatnumberofdigitsunlesstheuseraskedforthemby specifyingavalueforscale.Squarerootcanbehandledinjustthesamewayasmultiplication. Theoperationofdivisiongivesarbitrarilymanydecimalplacesandthereissimplynowayto guesshowmanyplacestheuserwants.Inthiscaseonly,theusermustspecifyascaletogetany decimalplacesatall. Thescaleofremainderwaschosentomakeitpossibletorecreatethedividendfromthequotientandremainder.Thisiseasytoimplement;nodigitsarethrownaway.

-8-References [1]L.L.Cherry,R.Morris,BC−AnArbitraryPrecisionDesk-CalculatorLanguage. [2]K.C.Knowlton,AFastStorageAllocator,Comm.ACM8,pp.623-625(Oct.1965).