Friday, April 6, 2018

GRAFIT Course Material - Newton-Raphson Approximate Ray Shooting Queries, Factoring, Diophantine Equations

--------------------------------------------------------------------------------------------------------------
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: