Newton's Method for nth root, as an integer arithmetic for Computers

 The actual values of my previous post are truly astronomical, and when I reviewed my python3 implementation, I found I re-invented the wheel differently on paper. Here is my python3 code, with comments: It is slightly more conservative with actual values.

By experiment, it gives very good square roots for 3 - 8, at 4 iterations

############## main program ###############################

#

# This script attempts to calculate the nth root of k

#

#########################################################


k = int(input("Enter the number we are taking the root of: "))

n = int(input("Enter the power of the root: "))

i = int(input("How many iterations would you like to try? "))

a = k

b = n


#########################################################

#

#   The formula for the Convergence Method is: x_k+1 = x_k - {[x_k^n]- K

#                                                             n[x_k]^n-1}

#   This is also represented as

#

#         [n-1/n (x_k)]+ [K/n * (1/x_k^n-1)]

#

#   Doing algebra and representing x_k as a/b, I got:

#

#    n-1     a      +     K     b^n-1

#   ----- * ---          --- * -------

#     n      b            n     a^n-1

#

#   Simplifying, this works out to:

#

#    (n-1) * (a) (a)^n-1  +  K * b * b^n-1

#   ---------------------------------------

#                 n * b * a^n-1

#

#     multiplying the a's and the b's, this results in three terms:

#

# (n-1) * (a)^n   +   K * (b)^n

# ------------------------------ (be careful not to square the n in the denominator)

#         n * b * a^n-1       

#

# Now I was able to recursively iterate with integer values. Compute each value

# first, before iterating, or a will influence b adversely

#    

count = 0

while(count<i):

    x = ((n-1)*(a**n))+(k*(b**n))

    y = (n*b)*(a**(n-1))

    a = x

    b = y

# The math.gcd(a,b) function computes the largest number that divides both a and b

# If there is are common factors, gcd(a,b) figures out their product

    x = math.gcd(a,b)

    if(x!=0):

        a = a // x

        b = b // x

# Divide both a and b by greatest common denominator

    count+=1

print()

print("x = " + str(a) + " // " + str(b))
print()
print("To evaluate the result: ")
# Another way to compute nth root.
x = math.log10(k)
p = x/n
p = 10**p
print("The answer is likely very close to " + str(p))

Comments

Post a Comment

Popular posts from this blog

A Question About Erasthmus' Sieve

Students of Mathematics are familiar with Erasthmus' Sieve. 2     x 3          x                4       x 5               x 6     x     x 7 8     x 9          x 10       x          x 11 12     x     x 13 14     x 15          x     x 16     x 17 18     x     x 19 20     x          x 21          x 22     x 23 First, we strike all multiples of 2 up to the square root (5.) Then all multiples of 3, then all multiples of 5, etc. I wrote a digital implementation of the Sieve, and used the index creatively, to keep track of the multiples. To "strike" an integer, I set the value of the relevant array entry to 2. In writing the code, I soon observed that as I asked the machine not to look at 2's, the first prime was an obstacle. To overcome this, I wrote a separate loop for 2's, and then began from three, only using the "strike array entry" function only on non-2 array entries. This was very satisfactory, and I was able to develop a list of all primes < 2 ** 2
Read more

Notice of corrupted results: Vigenere may yet be found to be a "group."

Retraction: It is with regret that I do not delete the previous post. I am an individual, not an organization, and I failed to adequately double-check my results, but I am leaving the post to maintain some accountability. I am able to definitively say that the script for 2chars_from_file.py DOES NOT yield an exhaustive list. It develops the ciphertext for all 2 Char combinations of the FIRST 10, three character ciphertexts. This is not due to a logic error, but rather there is a virus that corrupts the indentation of the two write statements.  This may be verified by downloading the relevant code, and examining it, and running it if needed, against the relevant datafile. It is difficult to be exhaustively correct about ALL of the scripts. This calls ALL of my results in question, with regard to the qualification of a mathematical group. If Vigenere IS a group, the resulting substitution is still valid, but there exist 6 Char passwords that will accomplish the same encryption in ONE STE
Read more

A Simple Rule for the Stock Market

The Stock Market is where the wealth of America is stored. As such, it is best when the stock market faithfully reflects the ups and downs of the economy. Stock market corrections are how the stock market reflects setbacks to the economy. This is good, as far as it goes, but in fact, when a stock market correction occurs, it is not well understood where the value of labor, goods and services stored in the stock market goes.  The whole idea that rising stock prices reflect improvements in the economy, is that this is the result of good investments. Investing is an act of devoting time, effort, or energy to a particular undertaking with the expectation of a worthwhile result. An investment is proven to be a good one, when it pays off after a duration of time. If you buy a stock, you wait for it to rise in price, and sell it at the appropriate time. "Buy low, Sell high," is how stock brokers explain their craft. How long should you hold a stock? This has always been up to the ow
Read more