Finding square roots using long division. - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: Finding square roots using long division. (/thread-32624.html) Pages:
1
2
|
Finding square roots using long division. - jahuja73 - Feb-22-2021 Below is code for long division based finding square root. But, it fails for decimals, as well as non-square integers. I mean it gives the same result for 1225, and 1235, i.e. 35. INFINITY_ = 9999999 def sqrtByLongDivision(n,l): i = 0 udigit, j = 0, 0 # Loop counters cur_divisor = 0 quotient_units_digit = 0 cur_quotient = 0 cur_dividend = 0 cur_remainder = INFINITY_ #print 'length of input:', len(n) a = [0]*l # Dividing the number into segments while (n > 0): a[i] = int( n % 100) n = int(n // 100) i += 1 # Last index of the array of segments i -= 1 for j in range(i, -1, -1): cur_remainder = INFINITY_ cur_dividend = cur_dividend * 100 + a[j] for udigit in range(10): if (cur_dividend - (cur_divisor * 10 + udigit) * udigit >= 0): #if ( (cur_remainder >(cur_dividend - ((cur_divisor * 10 + udigit) * udigit))) and (cur_dividend - ((cur_divisor * 10 + udigit) * udigit) >= 0)): # Calculating the remainder cur_remainder = cur_dividend - ((cur_divisor * 10 + udigit)* udigit) # Updating the units digit of the quotient quotient_units_digit = udigit if cur_remainder == 0: print 'Exiting: cur_remainder ==0' break print ('New rem. :', cur_remainder) else: print(' else break') break # Adding units digit to the quotient cur_quotient = cur_quotient * 10 + quotient_units_digit # New divisor is two times quotient cur_divisor = cur_quotient * 2 # Including the remainder in new dividend cur_dividend = cur_remainder return cur_quotient # Driver code x = 1235.789 # Find length of integer y=x length =0 while (y > 0): y //=100 length+= 1 print 'length :', length print(sqrtByLongDivision(x, length))Also, hope once can find the square root for non-square integers, can also find for decimals. RE: Finding square roots using long division. - Serafim - Feb-22-2021 The long division method, such as you have programmed it gives you the integer part of the square root, so it is correct that you get 35 both for 1225 and for 1235 as you stop counting when you have used the full length of the array ("a" in your code). If you want to continue beyond this you must add new groups of zeroes to "a", one group for the number of decimals you want Eg. the square root of 3: With your method you get 1. Next step, decide the number of decimals, say 3. Extend "a" to [03, 00, 00, 00] and count with the same method 1.732 --------------- 3.000000 1 1 200 27 189 1100 343 1029 7900 3462 6924 176You can experiment with your own code and use 1225000000 => 35000, while 1235000000 => 35142. It is just a matter of where to place the decimal point... RE: Finding square roots using long division. - jahuja73 - Feb-22-2021 (Feb-22-2021, 09:54 AM)Serafim Wrote: If you want to continue beyond this you must add new groups of zeroes to "a", one group for the number of decimals you want Thanks, seems easy for integers, but still clueless for floats as 1235.6789. The coding is too difficult as have jobs: 1. In the driver code, need know length of float. Need break in units of two based on that.. If make modifications in the Driver code as follows: #Driver code x = 1235.789 # Find length of integer y=x length =0 """ while (y > 0): y //=100 length+= 1 """ while (y > 0): if (y>=1): print 'integer part' y = y //100 print 'y :', y length += 1 elif (y <1) : print 'decimal part' y = y*100 y /= 100 print 'y :', y length += 1Then, get: Output: integer part y : 12.0 integer part y : 0.0 length : 2 Unable to find a way out. RE: Finding square roots using long division. - Serafim - Feb-22-2021 It is actually pretty easy. No need to break it up into an integer and a decimal part. Say you want 10 decimals for the square root of 1235.789 (taken from your program). Then multiply the value with 1020 = 123578900000000000000000 Running your function on it gives 351537906917. Divide by 1010 = 35.1537906917 Correct answer! If you want many decimals, then don't calculate the answer as an integer, just keep the figures calculated in a list [3, 5, 1, 5, 3, 7, 9, 0, 6, 9, 1, 7]. The length of the list minus the number of decimals tells you where to place the decimal point. RE: Finding square roots using long division. - Serafim - Feb-24-2021 I have made an implementation that needs some explanation.
def sqrtLongDiv(n, d=0): a, d = prepare(n, d) # See the comment in the explanation b = '' # Here we collect the result drange = range(10)[::-1] divisor = 0 dividend = 0 remainder = 0 quotient = 0 unit = 0 dec_point = len(a)-d # the position of the decimal point for i in range(len(a)): if i == dec_point: # Insert the decimal point here b += '.' dividend = dividend * 100 + a[i] # Calculate the new dividend for dig in drange: # Testing with 9,8,..,0 gives simple stop condition if (divisor * 10 + dig) * dig <= dividend: # collect the resulting digit b += str(dig) # calculate the reminder remainder = dividend - ((divisor * 10 + dig) * dig) # Remember the newly calculated digit unit = dig # and break out as we have found a correct digit break # Calculate the new intermediary quotient quotient = quotient * 10 + unit # as well as the new intermediary divisor divisor = quotient * 2 # and let the calculated remainder become the base for the next dividend dividend = remainder return normalize(b)Below there is a test run (I slightly changed the return value for the sake of the show). All results are verified by WolframAlpha (some are as predictednot correctly rounded-off in the last decimal) RE: Finding square roots using long division. - jahuja73 - Feb-24-2021 (Feb-24-2021, 09:52 AM)Serafim Wrote: I have made an implementation that needs some explanation. 1. Though simple, request the two modules: 'prepare', 'normalize' for the sake of consistency. 2. It seems the parameter 'd' to prepare is user defined. The only way to custom (input based) definition seems to convert input to string, and check for decimal. Say, '.' in string (if correct). Then, based on number of digits after decimal, can decide value of 'd'. Cannot though think of a criteria. 3. The possible flaw referred by you should be due to limited number of decimal digits? If yes, then the accuracy is affected. If so, then rounding is to be done by a seperate module? RE: Finding square roots using long division. - Serafim - Feb-24-2021 Here goes: def prepare(n, d): a = [] m = str(n) int_part = '' dec_part = '' if '.' in m: int_part, dec_part = m.split('.') else: int_part = m if len(int_part) % 2 != 0: int_part = '0' + int_part for i in range(0, len(int_part), 2): a.append(int(int_part[i:i+2])) if len(dec_part) % 2 != 0: dec_part += '0' for i in range(0, len(dec_part), 2): a.append(int(dec_part[i:i+2])) min_dec = len(dec_part) // 2 d = max (d, min_dec) for i in range(min_dec, d): a.append(0) return (a, d) def normalize(s): if '.' in s: while s[-1] == '0': s = s[:-1] if s[-1] == '.': s = s[:-1] while len(s) > 1 and s[0] == '0' and s[1] != '.': s = s[1:] return s RE: Finding square roots using long division. - Serafim - Feb-24-2021 I didn't answer your last question (3): I think normalize is the place. Add one digit to the decimals and then shorten the result. It's a messy business as the result is actually a string. Maybe consider the two last digits as a decimal number and round it of as an integer. Then replacing the two last digits in the result string by that integer. E.g. the last two digits = '37' => 3.7 => rounded to 4 and replace '37' by '4'. Maybe there are other ways. RE: Finding square roots using long division. - jahuja73 - Feb-24-2021 (Feb-24-2021, 11:01 AM)Serafim Wrote: I didn't answer your last question (3): Very bold answer as never got this detail printed anywhere on SO. Seems they want reader to figure it out. But came only near to this idea. But, still (after your answer) feel to comprehend fully need code or at least elaborate algorithm. Thanks in anticipation. RE: Finding square roots using long division. - Serafim - Feb-24-2021 Sorry, I am off to my next project. Try implementing it yourself. It is not that big an effort. Use my hint in previous message and the round() function. That would do the trick. By the way, I found the code that you have copied "your" implementation from. Seems like you have taken someone elses code and want us to explain why it doesn't work the way you want it to work. I think I explained why. My implementation is based on the fact that squareroot(100*x) = 10 * squareroot(x). |