Programming Assignment 2 Solution

Computing Square Root Using the Bakhshali Method

Bakhshali method is a method for finding an approximation to a square root. The method wasdescribed in an ancient Indian mathematical manuscript. It computes the square root of a given number iteratively and the number of correct digits of the approximation roughly quadruples with each iteration. To calculate𝑆,the method first generates an integer𝑥!that is the nearestperfect

squarerootto𝑆,i.e.,𝑥!!isaninitialapproximationto𝑆.Thenthemethodsuccessivelyiterates

the result with the following formulas (𝑛 ≥ 1):

𝑆−𝑥!!!!

?!=

2𝑥!!!
𝑏!=𝑥!!!+𝑎!

𝑎!!

?!=𝑏!−2𝑏!

After𝑛iterations,themethodoutputstheapproximatedresult𝑥!.

Example:
Let𝑆 = 125348and𝑥!= 600(other initial approximations are also fine, the number of iterationsneededtoproduceapreciseresultdependsonthisvalue).Then,thefirstiterationgives:



𝑎!

=125348 − 600×600= −195.543

2×600
𝑏!= 600 + (−195.543) = 404.456



𝑥!

= 404.456 −




2×404.456

= 357.186



Likewise, the second iteration gives:






𝑎!

=125348 − 357.186×357.186= −3.126

2×357.186
𝑏!= 357.186 + (−3.126) = 354.06



𝑥!

= 354.06 −(−3.126)×(−3.126)= 354.046

2×354.06






Programming Tasks:
Please implement the Bakhshali method as a Java program (Bakhshali.java). The program will prompt for a number𝑆,of which the square root will be computed. In this task, you only need to perform one iteration of the Bakhshali method. After computation, your programshoulddisplaytwovaluesonthescreen:(1)theinitialapproximation𝑥!and(2)the
approximated square root after one iteration (i.e.,𝑥!), which should contain six decimal places. You are not allowed to use library methods to compute square roots. Simple arithmetic operations are sufficient to solve thisproblem.

Inthesecondtask,youshouldimproveyourprogramforthefirsttask.Thesecondprogram (Bakhshali2.java)willstillpromptforanumber𝑆.Thedifferenceisthatitwillperforman indefinitenumberofiterationsuntilthedifferencebetweentwoconsecutiveapproximationsofsquarerootsissmallerthanorequalto1×10!!.Aftercomputation,yourprogramshoulddisplaythefollowingvalues,ofwhichallfloatingpointvaluesshouldcontainsixdecimalplaces:(1)theinitialapproximation𝑥!,(2)theapproximatedsquarerootaftereachiteration, and(3)thesquarerootcomputedbycallingthelibrarymethodMath.sqrt(doublenum).
Note:Inbothtasks,theinitialapproximation𝑥!(aninteger)shouldsatisfythefollowingproperty:

𝑥!!≤ 𝑆and there does not exist any other integer𝑥such that𝑥 𝑥!∧𝑥!≤ 𝑆.

We provide screenshots of some sample runs below. Your programs should also be able to deal with invalid inputs (e.g., a negative𝑆).




Sample input and output of Bakhshali.java:




Input:38.222x0 = 6

x1 = 6.182395

Figure 1. Running Bakhshali method with one iteration




Input:-3error

Figure 2. Running Bakhshali method with an invalid input




Sample input and output of Bakhshali2.java:




Input:38.222x0 = 6

x1 =6.182395

x2 =6.182394

Library:6.182394

or




Input:456.234x0 = 21

x1 =21.359635

x2 =21.359635

Library:21.359635

Figure 3. Running Bakhshali method with indefinite iterations (two examples)




The submission deadline is 5:00 PM, April 8th(Sunday).






Requirements:

Please name the two java source files asBakhshali.javaandBakhshali2.java.Do not use othernames.
No package is needed in your.javafile.
Chinese characters or other special symbols shouldn’t appear in yourprograms.
Please put the two.javafiles into one folder named as your student ID (such as 11710001), then compress it to a.zipfile and upload the zip file to Sakai before thedeadline.
The formats of input and output must strictly follow the samples.