use strict;
use warnings;

=pod Algorithm

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit_by_digit_calculation

Write the decimal expansion of the square. The numbers are laid out in a fashion similar to the long division algorithm, and the root will appear above its square. Divide the digits of the square into pairs, starting from the decimal point and going both left and right. The decimal point of the root should be placed above the decimal point of the square. One digit of the root will appear above each pair of digits of the square.

Begin at the left-most (non-zero) pair of digits of the square. Initialize the remainder to zero. Initialize p to zero.
For each iteration (pair of digits) do:

   1. Bring down the most significant (leftmost) pair of digits of the square not yet used (if all the digits have been used, use the digits 00) and append them to the remainder from the previous step, i.e. multiply the remainder by one hundred and add the two digits. This will be the current value c.
   2. Let p be the part of the root found so far, ignoring any decimal point (for the first step, p = 0). Determine the greatest digit x such that y = (20 \cdot p + x) \cdot x does not exceed c (notice 20p + x is simply twice p, with the digit x appended to the right). You can find x by guessing what c/(20·p) is and doing a trial calculation of y, then adjusting x upward or downward as necessary. Place the digit x as the next digit of the root, i.e above the two digits of the square which you just brought down. Thus the next p will be the old p times 10 plus x.
   3. Subtract y from c to form a new remainder.
   4. If the remainder is zero and there are no more digits to bring down, then the algorithm has terminated. Otherwise go back to step 1 for another iteration.

=cut

$|++;
use Data::Dumper;
use bignum;

my $number = "5.0";
my ($front, $back) = split '\.', $number;
$front = '0' . $front if length $front % 2;
$back .= '0'          if length $back % 2;
print "Front $front, Back $back\n";
my @digits;
push @digits, grep {length} split(/(..)/, $front), ".", grep {length} split(/(..)/, $back);
print "Digits ", join("-", @digits), "\n";

my $i = 0;
my $remainder = 0;
my $p = 0;    # root without decimal
my $root = 0; # root with decimal
my $x = 0;
my $y = 0;
my $c = 0;
while ($i < 10_000) {
	my $pair = shift @digits;
	$pair ||= '00';
	if ($pair eq '.') {
		$root .= '.';
		print "$i\t.\n";
		next;
	}
	$i++;
	$c = (100*$remainder) + $pair;
	$x = int($c / (20 - $p));
	$x = 0 if $x < 0;
	#print "Guessing X is $x when C = $c and P = $p\n";
	$y = ((20 * $p) + $x)  * $x;
	if ($y <= $c) {
		while (1) {
			$x++;
			$y = ((20 * $p) + $x)  * $x;
			#print "X = $x, Y = $y, C = $c\n" if $i == 308;
			if ($y > $c) {
				$x--;
				$y = ((20 * $p) + $x)  * $x;
				last;
			}
		} 
	} elsif ($y > $c) {
		while (1) {
		    #print "X = $x, Y = $y, C = $c\n" if $i == 308;
			$x--;
			die if $x < 0;
			$y = ((20 * $p) + $x)  * $x;
			last if ($y < $c)
		} 
	}

	$p = $p . $x;
	$root = $root . $x;
	print "$i\t$x";
    #print "X = $x, Y = $y, C = $c";
	print "\n";
	$remainder = $c -$y;
	last if ($remainder == 0 and scalar @digits == 0);
}
print "\nAfter $i iterations:\nRoot=$root\n";

##</code><code>##

2.236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274969508176150773783504253267724447073863586360121533452708866778173191879165811276645322639856580535761350417533785003423392414064442086432539097252592627228876299517402440681611775908909498492371390729728898482088641542689894099131693577019748678884425089754132956183176921499977424801530434115035957668332512498815178139408000562420855243542235556106306342820234093331982933959746352271201341749614202635904737885504389687061135660045757139956595566956917564578221952500060539231234005009286764875529722056766253666074485853505262330678494633422242317637277026632407680104443315825733505893098136226343198686471946989970180818952426445962034522141192232912598196325811104170495807048120403455994943506855551855572512388641655010262436312571024449618789424682903404474716115455723201737676590460918529575603577984398054155380779064393639723028756062999482213852177348592453515121046345555040707227872421534778752911212121184331789335191038008011118179004590618846249647104244248308880129406811314695953279447898998931691577460792461807500679877124204847380502773608291559913962448914943560683462529064408327944642680888989746046308353537875042061374757606883401879088192559117973574464190248537871146194090191913688035110397638436041281058110378698951852014697045642021763892890884446377826385893792440046028875405398460156061705223615090385775410042193684987254271850375215557693316723004778269866662446210678464272486385274578213410067985645305271124180595972849455195451310172309750871496529436282902540012047780324155464489988706177998190033606562243886409639287753517266295971438227956307956149523015444235016538917278640913041979397111356282139367457681174922067562108887818873671671627622623379877111539509682982890683018259081401003895509723261508452834587893607346396117236678366571982607921440289119008995584241522495712918323216741189975720139403788197728015288723418668345418382867300274315320229607628612524761028642346963020111802691220236015810127628430541861717618575140690101561629091763981267225965596282349067854624161857945584442659612858937564854974803490110813557514166474621951830235525956886569495816353036195574536832235265007722422582873668753404700742232661451739766517420672644476219618024220397983536829835024662680305467687674469001869572099585891983164402516209196461851057442482740872298204109437109922361752853153022121091762951208863569597169079462572603250897522297040434128808223321533901195515665140790221756461654212957878042231382078553676907726666431316593195462068720646450914872744082488128177653475168679073591862464426874641991499778939913129472014591999678257620639485262503594282864024622559103789556345382831782355983912962511600369101312659057197182001817243605955127578519983299892856386044587104693349518653903308428042182726036389445415780244174574723414697299996312510945622746959743313905497801628876810654967562756493383488845926982941631401470509141417954535093868764523909372306624190671584760292185470204202383804367213501946179150579154936284590867887709863106792607614583383516922029219901101296073586082944731440797201471015218046346250032264096871672963540969636219832048850465433443803786691927572175750574034787186060267180224742047834253180940526988056615337534872773026542125606463481386346689646871290637011627062170994667015199335574248981167273508265781724812649127907144250485223405560573120864698856746034511488116745565359920634787280265752554024873596622892873895341062544984820943340027649566257313012986868360780082035610679011754491733115104587831647941683545966745646230513852185991884480001121253357348715847944908169635303946872530537889777105440549557494671967073455522815183424102653868967505983299961872049235688535145553580038383814076104409224649647826522086543833690246120472557870908649235399515073780835273005095702764926293166727667520471557985345977264323716791807279963676916552898249196187408611111922759468652269660989899373621790713926965635625772507292168406789307638883891428533364743678983664741817149700533136079794881324210720612800521634225331990839873746321891445776218415576455440727336896306512345682353819585333310447693766227437059838432638104031372624456414311997529368471041185707435156153121007354626195038244794777444936516114319489148096859756147044319685335325156154124038860801085100316625006035068188234382038597807689450066597604900287359368833895919090609182062762324374091359957327323492119140006891940227050362692013131070406957762348299882549652830427113552788078142077417636467613606700076093600349616441182193688405289280437541068020063605763328830618278789631280638564557096482902100637765037994014972457588431179148564043331412437618115617610064935398259457442077414739481287133491784051731314795712171913306821407199566408926726929709789953277707020910545964845813996977073936560929194915253028687181018766424874866677410333142980118142113404977597160874363025220088076297608145048812328580449564543054482241701315776774249872702136127303334864446555355115947985407524638294094647910241214110079841768852074175816866685236768271941563296591074286439223790075954292600151119507591407104542898638264345112880256618361009001798437410242372138671463077918701580601473454046628330640846803107482885374308110232959222866460497088081881382291227974605207903656336068965050865347715180112086404907454385824972916266688339705987827149573979159728789960460942339343147245678240362546258331799055198384406367447136545587712746625309599718249265500601211851349099588701762385901137098651871063745828360227282437494150525621373966027152104943889118643910719220905660629767823538602393171668628849789797131168501668218859005543951667044885825147298761508342274784875202870136597569865425995024573763920996715503175435608213942639335069543895845273038032679542569478158672222382817996611206722121974343566110870807121790585816369282874278588756271209640778958251490154151150206004841453258003618084586849885181213322826645744539613802919890239909560327983028252250514565613286625233149387763902128843347743600022008436966051618330867674984728236777712937028630012746380859029629388486292179050941440748111338261384419816096389059502213009285621083551051819037426377671829531992082635920418830617171066477545076046545526595474428625593643343246884236640360576282549488633769443691878556287094819999814446640611852595322247665596663397650786252401300740576895657333880894615894209522511731675059724725019996464671943101446767666488163051556386728525260866053179163416009025577462318711754944345129894001032733451543078419681900654902243073746018243992590455318263274187937214542685385246309506608759866331622147392862843439588681127831024216216272525377713949613612023383788350054459748317398358290699892488838802439571720274732165738144473029542782537484193302757512411837086577766834858418031262665663871512441794275312619570031263099649128917308495858714456575012169629067027043634591758659823420064952444104389290210724901025976861742688879014488534702925723598366467291967392752654451513831944790876610417329494847630221585469896739047929585379873966498359990055790001209193226269267260498999029616106580358059503650317500980148703759670236720654455452034348090711433177111565945821239163870342110965158614182011527173980385944359903374623511262889712962004400285090811085854691767423204198958914416475608737437889611273783651604889992637566840549820306715821454672506578138669482476044440232525542386170897005908382640080199973113330355132819073123957956367609020607130202631789178057437221738117878942736029691400367329912944065886687485978928548251028718116869681839097403047228063478278072328803969101020982423395840024039992101398993280607017273858078820140389010640324697455264654648988792609617811085027594466295037041418205012737196335906096362014788490634004776095196686469008285168628127225442192045648467564561805595319215542169878303497746337554270447801823423470183720130924019804995170555850855633194076699011602125231066738218756931954210595004463461482435566883788236919317220596037557485489127733932255449007691721052830206081796515555089482306641528151763355029951076094232593355420117532923190993553854109924787971418510140548139956281686249930726143733067436121174844851963306141051476690831541085843259962298350172226235315463441912313129573909489785426412161270915589248290621339674842275963379276470666089557663386794574578362073281665397139765088770333517245798613928693697950296817580792952084072204120434347889405269752673087863904581547672334779623562484967311562100683389031272520860073314862169533097555602571558472908370448944723427484585116831862712257327433406561443431067852926514613461278217082177361714856771765612046066828171007819470774522690239258528319904255786227088629203054618051076542086519324534878074911272245722781566388671411800762974017973226307963917148846608839417133934445862854614827697655779511777215994774089404063336697138839819309605964986396353158536597112594460213655544703254815676148637556546364238393905601032175831442576526759364625451257400030003658595154599871581898392815268857231514270888557967660809094054203891600851640424046891612606900673162944370984073599799458707078393624266390330759490798222988488903660677176825808036356376427520133185698827355086349032108187742207374304232808116438689424089655519210833897290797566525390960278300380779918626134063732334132743928051385734277742932623783853713653839905529159954365575189219232344377362189093031577382448212196283945372385109575798526307189458456501610850338136280215635920437706615246111276326328038449090065153134785199530350616028543214286174377257196720749301142684093401668655084605540955866223673338064657706137477598142718014806098149197790272953752173568864764964378612351406391276064616394387271345483928774525174123086614592740762550303408120101151897654477126903127810531542085291895208111390191968177780752415991327760357237118318882234501846265595422760