Talk:Chakravala method: Difference between revisions
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WP India}}. Remove 1 deprecated parameter: field. Tag: |
|||
(31 intermediate revisions by 15 users not shown) | |||
Line 1: | Line 1: | ||
{{User:MiszaBot/config |
|||
{{Maths rating|class=Stub|importance=low|field=number theory}} |
|||
| algo = old(365d) |
|||
{{WP India |
|||
| archive = Talk:Chakravala method/Archive %(counter)d |
|||
|class=Stub |
|||
| counter = 1 |
|||
|importance= |
|||
| maxarchivesize = 150K |
|||
| archiveheader = {{Automatic archive navigator}} |
|||
| minthreadstoarchive = 1 |
|||
| minthreadsleft = 5 |
|||
}} |
}} |
||
{{WikiProject banner shell|class=Start| |
|||
{{WikiProject Mathematics|importance=low}} |
|||
{{WikiProject India|importance=low|assess-date=May 2012}} |
|||
}} |
|||
{{Archive box |search=yes |bot=Lowercase sigmabot III |age=12 |units=months |auto=yes }} |
|||
== The example == |
|||
There is something wrong with the example. In the very first iteration, we have "and take t so that the absolute value of m^2 − 67 is minimized. The result is t = − 2, m = 7, m^2 − 67 = − 18." But if we had taken t = 3 instead, then m = -8 and m^2 - 67 = -3, whose abs value is lower than -18. [[Special:Contributions/91.189.72.18|91.189.72.18]] ([[User talk:91.189.72.18|talk]]) 18:43, 21 February 2009 (UTC) |
|||
:Hmm, that seems right! The article needs to be fixed... How did you happen to catch it? [[User:Shreevatsa|Shreevatsa]] ([[User talk:Shreevatsa|talk]]) 19:41, 21 February 2009 (UTC) |
|||
::I've added an explanation. [[User:Xanthoxyl|Xanthoxyl]] ([[User talk:Xanthoxyl|talk]]) 19:53, 21 February 2009 (UTC) |
|||
::: Makes sense now. Perhaps we should include a general description of the method before the examples, including details like this. [[User:Shreevatsa|Shreevatsa]] ([[User talk:Shreevatsa|talk]]) 20:03, 21 February 2009 (UTC) |
|||
::::There's a similar problem with the second iteration t = -2 would produce a smaller value. The first exception (new x would be 0) doesn't apply. Why is it discarded? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.213.65.34|64.213.65.34]] ([[User talk:64.213.65.34|talk]]) 09:31, 1 April 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot--> |
|||
:::::Another problem in the second iteration, I think. The reasoning includes: "... |m2 − 67| is minimal for m = 5" but in the new solution from this iteration, m has been changed to 11: 90^2 - 67*11^2 = -7. The working for the next iteration uses m = 11 so this requires either a re-writing of the third iteration and subsequent working, or an explanation in the second iteration of why m = 11 is chosen although m = 5 gives the smallest value of |m^2 - 67| (excluding negative values of m). [[Special:Contributions/115.69.35.19|115.69.35.19]] ([[User talk:115.69.35.19|talk]]) 15:23, 1 January 2021 (UTC) |
|||
::::http://cs.annauniv.edu/insight/insight/maths/algebra/indet/chakra.htm shows a method that actually works <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/64.213.65.34|64.213.65.34]] ([[User talk:64.213.65.34|talk]]) 10:28, 1 April 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot--> |
|||
::::: I guess that's the method now found at: http://cs.annauniv.edu/insight/Reading/algebra/indet/chakra.htm. [[Special:Contributions/115.69.35.19|115.69.35.19]] ([[User talk:115.69.35.19|talk]]) 15:32, 1 January 2021 (UTC) |
|||
:::::It looks like t is also being chosen such that <math>m > 0</math>. This makes sense, since we want x and y to be increasing, so I've added a small change to point this out, but this should probably be explained better. It's not explicitly mentioned in the version you linked, either, but it seems it is also necessary that <math>p_r > 0</math> when following that version. [[User:Asztal|Asztal]] ([[User talk:Asztal|talk]]) 18:31, 4 May 2009 (UTC) |
|||
==Question== |
|||
How did Brahmagupta use this method to get the answer for N=61, because this method can be used to find other solutions for the equation Nx^2 + k = y^2 if and only if one set of value for x and y are known? The solution set for N=61 is the first set of solution using which other set of solutions can be found. So this simply means that Brahmagupta had used other method to solve. Can anyone explain? [[User:Ranjitr303|Ranjitr303]] ([[User talk:Ranjitr303|talk]]) 05:26, 25 June 2010 (UTC) |
|||
: No, the method can be used to solve Nx² + 1 = y² starting from a solution to Nx² + k = y² for ''any'' k. Thus for N=61, we have a solution (61)1² + 3 = 8², i.e. a solution x=1, y=8, k=3. Now iterate, etc. BTW, Brahmagupta did not solve the N=61 case; the article states it was solved by Jayadeva and Bhaskara II. [[User:Shreevatsa|Shreevatsa]] ([[User talk:Shreevatsa|talk]]) 21:24, 25 June 2010 (UTC) |
|||
== The cases where k is up to sign 1,2,4 == |
|||
The sentences " Optionally, we can stop when k is ±1, ±2, or ±4, as Brahmagupta's approach gives a solution for those cases." and "but since the right-hand side is among ±1, ±2, ±4, we can also use Brahmagupta's observation directly." are a bit unclear to me. What exactly is the observation, and how does one proceed? |
|||
[[User:Evilbu|Evilbu]] ([[User talk:Evilbu|talk]]) 13:39, 13 August 2012 (UTC) |
|||
== Amendments to the Chakravala Method for Solving Pell's Equation == |
|||
Amendments to the Chakravala Method for Solving Pell's Equation |
|||
Amendment 1 - Addition of Variable, f, to Vector |
|||
------------------------------------------------ |
|||
The current method uses a vector ( x_current, y_current, k_current) with k_current = x_current^2-Ny_current^2 |
|||
I propose to use a new vector ( f_new, x_new, y_new, k_new) with: |
|||
f_new = gcd(x_current, N) |
|||
x_new = x_current/gcd(x_current, N) |
|||
y_new = y_current and |
|||
k_new = f_new.x_new^2-N.y_new^2/f_new |
|||
The result of combining 2 vectors (f1, x1, y1, k1) and (f2, x2, y2, k2) is (1, f1x1f2x2+Ny1y2, f1x1y2+f2x2y1, f1f2k1k2) |
|||
Reduction of a vector is a 2-step process. |
|||
The first step is the current reduction step ( f, x, y, k)->( f'=f, x'=x/gcd(x, y), y'=y/gcd(x, y), k'=k/gcd(x, y)^2) |
|||
The second step is (f', x', y', k')->( f''=f'.gcd( x', N/f'), x''=x'/gcd( x', N/f'), y''=y', k''=k'/gcd( x', N/f') |
|||
The method for finding a starter vector and for finding a vector through the BIG M method now should search for the optimum |
|||
by using all factors of N < sqrt(N) for f. |
|||
Sometimes after a combination and reduction f > N/f. |
|||
To keep f < N/f it might be necessary to employ a transpose transformation. |
|||
( f, x, y, k) -> ( f_transpose = N/f, x_transpose = y, y_transpose = x, k_transpose = -k) |
|||
Amendment 2 - Direct Solutions When |k| is in {1, 2, 4} |
|||
------------------------------------------------------- |
|||
The current method would require that when k satisfies the condition above that the vector combine with itself (or sometimes |
|||
- when |k| = 4 - the first vector encountered with |k|=4) until k=1. |
|||
In the following cases the solution can be obtained directly: |
|||
k=1 and f=1 - x_solution = x , y_solution = y |
|||
|k| in { 1, 2} and not ( f=1 and k=1 ) - x_solution = (2fx^2-k)/|k| , y_solution = 2xy/|k| |
|||
|k| = 4 and f is even - x_solution = (fx^2-2sgn(k))^2/2-1 , y_solution = xy(fx^2-2sgn(k))/2 |
|||
k=4 and f=1 - x_solution = x(x^2-3)/2 , y_solution = y(x^2-1)/2 |
|||
|k| = 4 and f is odd and f > 1 - x_solution = fx^2(fx^2-3sgn(k))^2/2-1, y_solution = xy(fx^2-sgn(k))(fx^2-3sgn(k))/2 |
|||
If N is of the form f^2.x^2 plus or minus 1, 2 or 4 times f then a solution can be obtained without needing to look for a starter. |
|||
Amendment 3 - Before Resorting to Using BIG M, Search Previously Encountered Vectors for a Vector With Which to Combine |
|||
----------------------------------------------------------------------------------------------------------------------- |
|||
With the current method, if |k| is not in { 1, 2, 4}, the only option is to employ the BIG M method to obtain a vector. |
|||
However, a previously encountered vector would be suitable for combining with the current vector, if: |
|||
1) it is not the current vector or its transpose; and |k_prev.k_current| equals |
|||
i) 64 or 128 ( and mod( f_prev.x_prev.y_curr+f_curr.x_curr.y_prev, 4)=0); or |
|||
ii) 1, 2 or 4 times a prime squared; or |
|||
iii) 1, 2 or 4 times prime_1^2.prime_2 ( and there is a second previously encountered vector where |k| = prime_2 ) |
|||
In light of this, if no direct solution is possible, one of a pair (or triplet for iii) of candidate vectors that satisfy one |
|||
of the above conditions is a better starter vector than the one with lowest |k|. |
|||
Working Examples |
|||
==Details== |
|||
---------------- |
|||
Would be great if someone could add some actual ''details'' about how this method works - especially as the article claims it is very simple. [[User:Gandalf61|Gandalf61]] 08:16, 14 April 2006 (UTC) |
|||
N=28 (example of direct solution with |k|=4 and f is even) |
|||
Current Method |
|||
-------------- |
|||
Starter find ( floor(sqrt(N)), 1, floor(sqrt(N))^2-N) |
|||
and ( ceil(sqrt(N)), 1, ceil(sqrt(N))^2-N) |
|||
( 5, 1, -3) |
|||
( 6, 1, 8) |
|||
neither vector has |k| in { 1, 2, 4}, so choose vector with lower |k| |
|||
( 5, 1, -3) |k| not in { 1, 2, 4}, so use BIG M |
|||
( M, 1, M^2-N) |
|||
(5M+28, 5+M, -3(M^2-28)) we want mod(y=M+5,|-3|)=0 and |-3(M^2-N)| to be minimised => M=4 |
|||
( 48, 9, 36) reduce |
|||
( 16, 3, 4) |k| = 4, so combine with self |
|||
( 16, 3, 4) |
|||
( 508, 96, 16) reduce |
|||
( 127, 24, 1) k = 1, so solve |
|||
x_solution = x = 127 |
|||
y_solution = y = 24 |
|||
New Method |
|||
:I just added an "example", except that it's way too long, and I gave up before the answer was actually reached, because it's just so tedious. (Simple, but tedious.) If someone adds a proof that this method actually works, without any [http://www-groups.dcs.st-andrews.ac.uk/~history/Miscellaneous/Pearce/Lectures/Ch8_6.html ad-hoc final steps] or [http://www.math.sfu.ca/histmath/India/12thCenturyAD/Chakravala.html handwaving], I might add an implementation in [[C (programming language)|C]]; but if we can't prove that it will terminate, there's not much point in pursuing that route. --[[User:Quuxplusone|Quuxplusone]] 22:48, 4 December 2006 (UTC) |
|||
---------- |
|||
Starter find ( f, floor(sqrt(N)/f), 1, f.floor(sqrt(N)/f)^2-N/f) |
|||
and ( f, ceil(sqrt(N)/f), 1, f.ceil(sqrt(N)/f)^2-N/f) |
|||
for f = all factors of N < sqrt(N) |
|||
Set f=1 |
|||
( 1, 5, 1, -3) |
|||
( 1, 6, 1, 8) ignored because gcd( x, N/f ) > 1 |
|||
Set f=2 |
|||
( 2, 2, 1, -6) ignored because gcd( x, N/f ) > 1 |
|||
( 2, 3, 1, 4) |k| is in { 1, 2, 4} so we can stop and use this vector to solve the equation directly |
|||
x_solution = (fx^2-2sgn(k))^2/2-1 = 127 |
|||
y_solution = xy(fx^2-2sgn(k))/2 = 24 |
|||
N=46 (example where a previous candidate satisfies a condition in Amendment 3) |
|||
::It looks as if the is a little "bait and switch" between 61 and 67, as well as being unclear whether the 61 case was solved in the 7th, 9th or 12th centuries. --[[User:Rumping|Rumping]] ([[User talk:Rumping|talk]]) 15:03, 14 August 2008 (UTC) |
|||
Current Method |
|||
=============== |
|||
-------------- |
|||
I'm an algorithmist, not a number-theoretician, but most NT's I've spoken to agree with me that the ''chakravala'' is easiest viewed (and thus implemented) as a special type of CF (continued fraction). |
|||
Starter find ( floor(sqrt(N)), 1, floor(sqrt(N))^2-N) |
|||
and ( ceil(sqrt(N)), 1, ceil(sqrt(N))^2-N) |
|||
( 6, 1, -10) |
|||
( 7, 1, 3) |
|||
neither vector has |k| in { 1, 2, 4}, so choose vector with lower |k| |
|||
( 7, 1, 3)|k| not in { 1, 2, 4}, so use BIG M |
|||
( M, 1, M^2-N) |
|||
( 7M+46, M+7, 3(M^2-N)) we want mod(y=M+7,|3|)=0 and |3(M^2-46)| to be minimised => M=8 |
|||
( 102, 15, 54) reduce |
|||
( 34, 5, 6)|k| not in { 1, 2, 4}, so use BIG M |
|||
( M, 1, M^2-N) |
|||
( 34M+230, 5M+34, 6(M^2-46)) we want mod(y=5M+34,|6|)=0 and |6(M^2-46)| to be minimised => M=4 |
|||
( 34M+230, 5M+34, 6(M^2-46)) |
|||
( 366, 54, -180) |
|||
( 61, 9, -5)|k| not in { 1, 2, 4}, so use BIG M |
|||
( M, 1, M^2-N) |
|||
( 61M+414, 9M+61, -5(M^2-46)) we want mod(y=9M+61,|-5|)=0 and |-5(M^2-46)| to be minimised => M=6 <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/203.13.3.89|203.13.3.89]] ([[User talk:203.13.3.89|talk]]) 08:48, 5 September 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot--> |
|||
== Improving the description of the method == |
|||
The classical CF method (aka "English method") of solving Pell's equation involves an RCF (''Regular Continued Fraction''). |
|||
I think that the decription of the method can be made more clear and compact. For example, the paragraph starting with ''In the general method, ...'' can be changed to the following: |
|||
:''The chakravala method takes as an input a non-square number <math>N</math> and some solution <math>(a, b, k)</math> for that <math>N</math> such that <math>\gcd(a,b)=1</math>. In every iteration, <math>(a, b, k)</math> is composed with some trivial solution triple <math>(m, 1, m^2 - N)</math>. For appropriate <math>m</math>, the composition <math>(am + Nb, a+bm, k(m^2-N))</math> can be scaled down by applying [[Bhaskara's lemma]]'' |
|||
The ''chakravala'' corresponds (in CF terms) to the NSCF (''Nearest-Square Continued Fraction''). |
|||
The major additions and modifications are: |
|||
An Indian mathematician named A.A.K. Ayyangar noticed this in the 1930's, but his work remains relatively unknown (Selenius cites AAK's results but nevertheless manages to claim credit for himself for unravelling the "''true nature of chakravala''"). |
|||
*"''N'' cannot be a square", otherwise <math>m^2 - N</math> can get zero. |
|||
If you have an algorithm for RCF it is easily adapted to yield NSCF, and also to get another variant called NICF (''Nearest-Integer CF''). Both NSCF and NICF are optimal CF's (ie: are the shortest-length CF's possible). |
|||
*"for appropriate ''m'' the composition can be scaled down". As the decription mentions below, <math>a + bm</math> must be divisible by ''k'' for the scaling to work. |
|||
*the solution triple <math>(m, 1, m^2 - N)</math>, is now refered to as a "composition". This is to avoid repeating the phrase "solution triple", and show that it is an intermediate result. |
|||
In the next paragraph it can be mentioned that the ''m'' that minimizes <math>|m^2 - N|</math> is unique, but this is not very important. [[User:Nxavar|Nxavar]] ([[User talk:Nxavar|talk]]) 08:23, 1 April 2015 (UTC) |
|||
A friend of mine hosts a Number Theory website and we've co-written some papers on this. I'll come back with links when I can find them. |
|||
: I think we should be careful about remaining true to the historical sources, and not imposing our own understanding on it. Different authors had slightly varying methods, and it would be better to talk of how they used it, rather than projecting modern terminology onto it. (For example they'd never say "we use Bhaskara's lemma here" -- they had a procedure, and now (with our Greek-inspired axiomatic-deductive conception of mathematics) ''we'' can justify the steps and make it seem as if the steps follow logically from other known facts, but in truth probably the steps came first (with some understanding and justification no doubt) and a formal justification later. So that is my concern. [[User:Shreevatsa|Shreevatsa]] ([[User talk:Shreevatsa|talk]]) 20:25, 1 April 2015 (UTC) |
|||
[[User:DeadHead52|DeadHead52]] ([[User talk:DeadHead52|talk]]) 11:32, 12 September 2008 (UTC) |
|||
========= |
Latest revision as of 06:10, 30 January 2024
This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||
|
This page has archives. Sections older than 365 days may be automatically archived by Lowercase sigmabot III when more than 5 sections are present. |
The example
[edit]There is something wrong with the example. In the very first iteration, we have "and take t so that the absolute value of m^2 − 67 is minimized. The result is t = − 2, m = 7, m^2 − 67 = − 18." But if we had taken t = 3 instead, then m = -8 and m^2 - 67 = -3, whose abs value is lower than -18. 91.189.72.18 (talk) 18:43, 21 February 2009 (UTC)
- Hmm, that seems right! The article needs to be fixed... How did you happen to catch it? Shreevatsa (talk) 19:41, 21 February 2009 (UTC)
- I've added an explanation. Xanthoxyl (talk) 19:53, 21 February 2009 (UTC)
- Makes sense now. Perhaps we should include a general description of the method before the examples, including details like this. Shreevatsa (talk) 20:03, 21 February 2009 (UTC)
- I've added an explanation. Xanthoxyl (talk) 19:53, 21 February 2009 (UTC)
- There's a similar problem with the second iteration t = -2 would produce a smaller value. The first exception (new x would be 0) doesn't apply. Why is it discarded? —Preceding unsigned comment added by 64.213.65.34 (talk) 09:31, 1 April 2009 (UTC)
- Another problem in the second iteration, I think. The reasoning includes: "... |m2 − 67| is minimal for m = 5" but in the new solution from this iteration, m has been changed to 11: 90^2 - 67*11^2 = -7. The working for the next iteration uses m = 11 so this requires either a re-writing of the third iteration and subsequent working, or an explanation in the second iteration of why m = 11 is chosen although m = 5 gives the smallest value of |m^2 - 67| (excluding negative values of m). 115.69.35.19 (talk) 15:23, 1 January 2021 (UTC)
- http://cs.annauniv.edu/insight/insight/maths/algebra/indet/chakra.htm shows a method that actually works —Preceding unsigned comment added by 64.213.65.34 (talk) 10:28, 1 April 2009 (UTC)
- I guess that's the method now found at: http://cs.annauniv.edu/insight/Reading/algebra/indet/chakra.htm. 115.69.35.19 (talk) 15:32, 1 January 2021 (UTC)
- It looks like t is also being chosen such that . This makes sense, since we want x and y to be increasing, so I've added a small change to point this out, but this should probably be explained better. It's not explicitly mentioned in the version you linked, either, but it seems it is also necessary that when following that version. Asztal (talk) 18:31, 4 May 2009 (UTC)
Question
[edit]How did Brahmagupta use this method to get the answer for N=61, because this method can be used to find other solutions for the equation Nx^2 + k = y^2 if and only if one set of value for x and y are known? The solution set for N=61 is the first set of solution using which other set of solutions can be found. So this simply means that Brahmagupta had used other method to solve. Can anyone explain? Ranjitr303 (talk) 05:26, 25 June 2010 (UTC)
- No, the method can be used to solve Nx² + 1 = y² starting from a solution to Nx² + k = y² for any k. Thus for N=61, we have a solution (61)1² + 3 = 8², i.e. a solution x=1, y=8, k=3. Now iterate, etc. BTW, Brahmagupta did not solve the N=61 case; the article states it was solved by Jayadeva and Bhaskara II. Shreevatsa (talk) 21:24, 25 June 2010 (UTC)
The cases where k is up to sign 1,2,4
[edit]The sentences " Optionally, we can stop when k is ±1, ±2, or ±4, as Brahmagupta's approach gives a solution for those cases." and "but since the right-hand side is among ±1, ±2, ±4, we can also use Brahmagupta's observation directly." are a bit unclear to me. What exactly is the observation, and how does one proceed? Evilbu (talk) 13:39, 13 August 2012 (UTC)
Amendments to the Chakravala Method for Solving Pell's Equation
[edit]Amendments to the Chakravala Method for Solving Pell's Equation
Amendment 1 - Addition of Variable, f, to Vector
The current method uses a vector ( x_current, y_current, k_current) with k_current = x_current^2-Ny_current^2
I propose to use a new vector ( f_new, x_new, y_new, k_new) with:
f_new = gcd(x_current, N) x_new = x_current/gcd(x_current, N) y_new = y_current and k_new = f_new.x_new^2-N.y_new^2/f_new
The result of combining 2 vectors (f1, x1, y1, k1) and (f2, x2, y2, k2) is (1, f1x1f2x2+Ny1y2, f1x1y2+f2x2y1, f1f2k1k2)
Reduction of a vector is a 2-step process. The first step is the current reduction step ( f, x, y, k)->( f'=f, x'=x/gcd(x, y), y'=y/gcd(x, y), k'=k/gcd(x, y)^2) The second step is (f', x', y', k')->( f=f'.gcd( x', N/f'), x=x'/gcd( x', N/f'), y=y', k=k'/gcd( x', N/f')
The method for finding a starter vector and for finding a vector through the BIG M method now should search for the optimum by using all factors of N < sqrt(N) for f.
Sometimes after a combination and reduction f > N/f. To keep f < N/f it might be necessary to employ a transpose transformation. ( f, x, y, k) -> ( f_transpose = N/f, x_transpose = y, y_transpose = x, k_transpose = -k)
Amendment 2 - Direct Solutions When |k| is in {1, 2, 4}
The current method would require that when k satisfies the condition above that the vector combine with itself (or sometimes - when |k| = 4 - the first vector encountered with |k|=4) until k=1.
In the following cases the solution can be obtained directly:
k=1 and f=1 - x_solution = x , y_solution = y |k| in { 1, 2} and not ( f=1 and k=1 ) - x_solution = (2fx^2-k)/|k| , y_solution = 2xy/|k| |k| = 4 and f is even - x_solution = (fx^2-2sgn(k))^2/2-1 , y_solution = xy(fx^2-2sgn(k))/2 k=4 and f=1 - x_solution = x(x^2-3)/2 , y_solution = y(x^2-1)/2 |k| = 4 and f is odd and f > 1 - x_solution = fx^2(fx^2-3sgn(k))^2/2-1, y_solution = xy(fx^2-sgn(k))(fx^2-3sgn(k))/2
If N is of the form f^2.x^2 plus or minus 1, 2 or 4 times f then a solution can be obtained without needing to look for a starter.
Amendment 3 - Before Resorting to Using BIG M, Search Previously Encountered Vectors for a Vector With Which to Combine
With the current method, if |k| is not in { 1, 2, 4}, the only option is to employ the BIG M method to obtain a vector.
However, a previously encountered vector would be suitable for combining with the current vector, if:
1) it is not the current vector or its transpose; and |k_prev.k_current| equals
i) 64 or 128 ( and mod( f_prev.x_prev.y_curr+f_curr.x_curr.y_prev, 4)=0); or ii) 1, 2 or 4 times a prime squared; or iii) 1, 2 or 4 times prime_1^2.prime_2 ( and there is a second previously encountered vector where |k| = prime_2 )
In light of this, if no direct solution is possible, one of a pair (or triplet for iii) of candidate vectors that satisfy one of the above conditions is a better starter vector than the one with lowest |k|.
Working Examples
N=28 (example of direct solution with |k|=4 and f is even) Current Method
Starter find ( floor(sqrt(N)), 1, floor(sqrt(N))^2-N)
and ( ceil(sqrt(N)), 1, ceil(sqrt(N))^2-N)
( 5, 1, -3) ( 6, 1, 8) neither vector has |k| in { 1, 2, 4}, so choose vector with lower |k| ( 5, 1, -3) |k| not in { 1, 2, 4}, so use BIG M ( M, 1, M^2-N) (5M+28, 5+M, -3(M^2-28)) we want mod(y=M+5,|-3|)=0 and |-3(M^2-N)| to be minimised => M=4 ( 48, 9, 36) reduce ( 16, 3, 4) |k| = 4, so combine with self ( 16, 3, 4) ( 508, 96, 16) reduce ( 127, 24, 1) k = 1, so solve x_solution = x = 127 y_solution = y = 24
New Method
Starter find ( f, floor(sqrt(N)/f), 1, f.floor(sqrt(N)/f)^2-N/f)
and ( f, ceil(sqrt(N)/f), 1, f.ceil(sqrt(N)/f)^2-N/f)
for f = all factors of N < sqrt(N) Set f=1 ( 1, 5, 1, -3) ( 1, 6, 1, 8) ignored because gcd( x, N/f ) > 1 Set f=2 ( 2, 2, 1, -6) ignored because gcd( x, N/f ) > 1 ( 2, 3, 1, 4) |k| is in { 1, 2, 4} so we can stop and use this vector to solve the equation directly x_solution = (fx^2-2sgn(k))^2/2-1 = 127 y_solution = xy(fx^2-2sgn(k))/2 = 24
N=46 (example where a previous candidate satisfies a condition in Amendment 3) Current Method
Starter find ( floor(sqrt(N)), 1, floor(sqrt(N))^2-N)
and ( ceil(sqrt(N)), 1, ceil(sqrt(N))^2-N)
( 6, 1, -10) ( 7, 1, 3) neither vector has |k| in { 1, 2, 4}, so choose vector with lower |k| ( 7, 1, 3)|k| not in { 1, 2, 4}, so use BIG M ( M, 1, M^2-N) ( 7M+46, M+7, 3(M^2-N)) we want mod(y=M+7,|3|)=0 and |3(M^2-46)| to be minimised => M=8 ( 102, 15, 54) reduce ( 34, 5, 6)|k| not in { 1, 2, 4}, so use BIG M ( M, 1, M^2-N) ( 34M+230, 5M+34, 6(M^2-46)) we want mod(y=5M+34,|6|)=0 and |6(M^2-46)| to be minimised => M=4 ( 34M+230, 5M+34, 6(M^2-46)) ( 366, 54, -180) ( 61, 9, -5)|k| not in { 1, 2, 4}, so use BIG M ( M, 1, M^2-N) ( 61M+414, 9M+61, -5(M^2-46)) we want mod(y=9M+61,|-5|)=0 and |-5(M^2-46)| to be minimised => M=6 — Preceding unsigned comment added by 203.13.3.89 (talk) 08:48, 5 September 2014 (UTC)
Improving the description of the method
[edit]I think that the decription of the method can be made more clear and compact. For example, the paragraph starting with In the general method, ... can be changed to the following:
- The chakravala method takes as an input a non-square number and some solution for that such that . In every iteration, is composed with some trivial solution triple . For appropriate , the composition can be scaled down by applying Bhaskara's lemma
The major additions and modifications are:
- "N cannot be a square", otherwise can get zero.
- "for appropriate m the composition can be scaled down". As the decription mentions below, must be divisible by k for the scaling to work.
- the solution triple , is now refered to as a "composition". This is to avoid repeating the phrase "solution triple", and show that it is an intermediate result.
In the next paragraph it can be mentioned that the m that minimizes is unique, but this is not very important. Nxavar (talk) 08:23, 1 April 2015 (UTC)
- I think we should be careful about remaining true to the historical sources, and not imposing our own understanding on it. Different authors had slightly varying methods, and it would be better to talk of how they used it, rather than projecting modern terminology onto it. (For example they'd never say "we use Bhaskara's lemma here" -- they had a procedure, and now (with our Greek-inspired axiomatic-deductive conception of mathematics) we can justify the steps and make it seem as if the steps follow logically from other known facts, but in truth probably the steps came first (with some understanding and justification no doubt) and a formal justification later. So that is my concern. Shreevatsa (talk) 20:25, 1 April 2015 (UTC)