--------------------------------------------------------------------------------------------------------------

Newton-Raphson Recurrence for Approximate Square Root of an Integer and Approximate Ray Shooting Queries for

Computational Geometric Factorization - 5 April 2018, 6 April 2018

--------------------------------------------------------------------------------------------------------------

Approximate Square of and integer N by Newton-Raphson recurrence is:

X(n+1) = 0.5*(X(n) + N/X(n))

Following result can be proved by elementary arithmetic:-

--------------------------------------------------------

Theorem:

--------

Any integer N can be written as N=a^2-b^2 for exactly one a,b and a^2 is a square in the vicinity such that N < a^2.

Proof:

------

N=a^2-b^2 is the special case of Diophantine Equation a^2x^2 + c = y^2 or y^2 - a^2x^2 = c.

Setting a=1, yields the previous form of diophantine equation c = y^2 - x^2. This was solved by Brahmagupta's Chakravala Cyclic Composition (Samasa) Deterministic Algorithm and Bhaskara's Lemma - https://en.wikipedia.org/wiki/Chakravala_method. Following is an alternative polylogarithmic time monte carlo algorithm for solving this Diophantine.

N = pq for factors p,q

N can be written as N = [(p+q)/2 + (p-q)/2]*[(p+q)/2 - (p-q)/2] for a=(p+q)/2 and b=(p-q)/2 and Theorem follows.

Example: 7*3=21 is written as (5+2)(5-2)=((7+3)/2+(7-3)/2)*((7+3)/2-(7-3)/2) and uniqueness is from unique factorization.

Approximate factors can be found by efficiently locating a, obeying condition N < a^2. Algorithm for this is as below:

iterate_for_polylogarithmic_steps_(O((logN)^c))

{

# Find approximate square root of N by newton-raphson recurrence

# Round off the approximate square root to nearest integer for candidate a

# candidate(a)^2-N = candidate(b)^2 after newton-raphson recurrence round-off again

}

This finds factors exactly mostly by solving for p,q from a=(p+q)/2 and b=(p-q)/2 and approximately sometimes.

This is an alternative to Hardy-Ramanujan Ray Shooting Queries mentioned in:

https://sourceforge.net/p/asfer/code/HEAD/tree/asfer-docs/AstroInferDesign.txt

and

https://github.com/shrinivaasanka/asfer-github-code/blob/master/asfer-docs/AstroInferDesign.txt

Newton-Raphson Recurrence for Approximate Square Root of an Integer and Approximate Ray Shooting Queries for

Computational Geometric Factorization - 5 April 2018, 6 April 2018

--------------------------------------------------------------------------------------------------------------

Approximate Square of and integer N by Newton-Raphson recurrence is:

X(n+1) = 0.5*(X(n) + N/X(n))

Following result can be proved by elementary arithmetic:-

--------------------------------------------------------

Theorem:

--------

Any integer N can be written as N=a^2-b^2 for exactly one a,b and a^2 is a square in the vicinity such that N < a^2.

Proof:

------

N=a^2-b^2 is the special case of Diophantine Equation a^2x^2 + c = y^2 or y^2 - a^2x^2 = c.

Setting a=1, yields the previous form of diophantine equation c = y^2 - x^2. This was solved by Brahmagupta's Chakravala Cyclic Composition (Samasa) Deterministic Algorithm and Bhaskara's Lemma - https://en.wikipedia.org/wiki/Chakravala_method. Following is an alternative polylogarithmic time monte carlo algorithm for solving this Diophantine.

N = pq for factors p,q

N can be written as N = [(p+q)/2 + (p-q)/2]*[(p+q)/2 - (p-q)/2] for a=(p+q)/2 and b=(p-q)/2 and Theorem follows.

Example: 7*3=21 is written as (5+2)(5-2)=((7+3)/2+(7-3)/2)*((7+3)/2-(7-3)/2) and uniqueness is from unique factorization.

Approximate factors can be found by efficiently locating a, obeying condition N < a^2. Algorithm for this is as below:

iterate_for_polylogarithmic_steps_(O((logN)^c))

{

# Find approximate square root of N by newton-raphson recurrence

# Round off the approximate square root to nearest integer for candidate a

# candidate(a)^2-N = candidate(b)^2 after newton-raphson recurrence round-off again

}

This finds factors exactly mostly by solving for p,q from a=(p+q)/2 and b=(p-q)/2 and approximately sometimes.

This is an alternative to Hardy-Ramanujan Ray Shooting Queries mentioned in:

https://sourceforge.net/p/asfer/code/HEAD/tree/asfer-docs/AstroInferDesign.txt

and

https://github.com/shrinivaasanka/asfer-github-code/blob/master/asfer-docs/AstroInferDesign.txt

## No comments:

Post a Comment