WP 34S Programme to solve Cornacchia's equation - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: Not HP Calculators (/forum-7.html) +--- Forum: Not quite HP Calculators - but related (/forum-8.html) +--- Thread: WP 34S Programme to solve Cornacchia's equation (/thread-1286.html) WP 34S Programme to solve Cornacchia's equation - Gerald H - 05-10-2014 07:00 PM The programme COR finds integer solutions for x & y given D & P in Cornacchia’s equation x^2 + D*y^2 = P P a prime number, D? Y 17 x<>Y 18 R↓ 19 LBL 01 20 RCL 11 21 x≥? Y 22 GTO 02 23 R↓ 24 x<>Y 25 RCL Y 26 MOD 27 GTO 01 28 LBL 02 29 R↓ 30 STO Y 31 x^2 32 RCL 01 33 x<>Y 34 - 35 RCL/ 12 36 √ 37 ENTER 38 FP 39 x≠0? 40 GTO 02 41 R↓ 42 RTN 43 LBL 02 44 CLx 45 END The programme MSR finds the square root modulo a prime or returns 0 if there is none. So for s^2 = t modulo p Input stack level y: t stack level x: p Returns stack level x: s MSR uses one sub-programme, KRN (see below), to find the quadratic nature of t relative to p. 1 LBL 'MSR' 2 DECM 3 STO 01 4 MOD 5 STO Y 6 √ 7 ENTER 8 FP 9 x≠0? 10 GTO 07 11 R↓ 12 RTN 13 LBL 07 14 RCL Z 15 STO 06 16 RCL 01 17 XEQ 'KRN' 18 1 19 + 20 x=0? 21 RTN 22 RCL 01 23 4 24 MOD 25 1 26 - 27 x=0? 28 GTO 08 29 RCL 06 30 RCL 01 31 1 32 + 33 4 34 / 35 RCL 01 36 BASE 10 37 ^MOD 38 DECM 39 RTN 40 LBL 08 41 STO 07 42 RCL 01 43 DSE X 44 LBL 00 45 STO Y 46 2 47 MOD 48 x≠0? 49 GTO 01 50 R↓ 51 RCL/ L 52 INC 07 53 GTO 00 54 LBL 01 55 R↓ 56 STO 08 57 1 58 STO 09 59 LBL 02 60 1 61 STO+ 09 62 RCL 09 63 RCL 01 64 XEQ 'KRN' 65 1 66 +/- 67 x≠? Y 68 GTO 02 69 RCL 09 70 RCL 08 71 RCL 01 72 BASE 10 73 ^MOD 74 DECM 75 STO 10 76 RCL 07 77 STO 09 78 RCL 06 79 1 80 +/- 81 RCL+ 08 82 2 83 / 84 RCL 01 85 BASE 10 86 ^MOD 87 DECM 88 STO 05 89 RCL 06 90 RCL 01 91 BASE 10 92 *MOD 93 DECM 94 STO Y 95 x<> 05 96 RCL 01 97 BASE 10 98 *MOD 99 DECM 100 LBL 04 101 STO 06 102 1 103 x=? Y 104 GTO 05 105 STO 07 106 R↓ 107 LBL 06 108 ENTER 109 ENTER 110 RCL 01 111 BASE 10 112 *MOD 113 DECM 114 1 115 x=? Y 116 GTO 03 117 STO+ 07 118 R↓ 119 GTO 06 120 LBL 03 121 RCL 10 122 2 123 RCL 09 124 RCL- 07 125 1 126 - 127 y^x 128 RCL 01 129 BASE 10 130 ^MOD 131 DECM 132 STO 04 133 ENTER 134 ENTER 135 RCL 01 136 BASE 10 137 *MOD 138 DECM 139 STO 10 140 RCL 07 141 STO 09 142 RCL 05 143 RCL 04 144 RCL 01 145 BASE 10 146 *MOD 147 DECM 148 STO 05 149 RCL 06 150 RCL 10 151 RCL 01 152 BASE 10 153 *MOD 154 DECM 155 GTO 04 156 LBL 05 157 RCL 05 158 END The programme KRN finds the Kronecker symbol, K(a,b), for two integers; K(a,b) is a generalization of the Jacobi symbol, itself a generalization of the Legendre symbol, & for our purposes returns whether the "a” in question is a quadratic residue modulo prime "b”, resulting in 1 for a quadratic residue, -1 for a non residue & 0 if the numbers have a common factor > 1. Input stack level y: a stack level x: b Returns stack level x: 1 or 0 or -1 1 LBL 'KRN' 2 x=0? 3 GTO 00 4 STO 04 5 x<>Y 6 STO 02 7 2 8 MOD 9 x<>Y 10 RCL L 11 MOD 12 + 13 x=0? 14 RTN 15 SIGN 16 STO 03 17 CLx 18 XEQ 01 19 RCL 02 20 x<> 04 21 STO 02 22 x≥0? 23 GTO 03 24 ABS 25 STO 02 26 RCL 04 27 SIGN 28 x=0? 29 INC X 30 STO* 03 31 LBL 03 32 RCL 04 33 x=0? 34 GTO 04 35 CLx 36 XEQ 01 37 RCL 04 38 4 39 MOD 40 RCL 02 41 RCL L 42 MOD 43 * 44 9 45 x=? Y 46 +/- 47 SIGN 48 STO* 03 49 RCL 04 50 ABS 51 ENTER 52 x<> 02 53 x<>Y 54 MOD 55 STO 04 56 GTO 03 57 LBL 01 58 RCL 04 59 2 60 MOD 61 x≠0? 62 GTO 02 63 # 1/2 64 STO* 04 65 RCL+ Z 66 GTO 01 67 LBL 02 68 R↓ 69 FP 70 x=0? 71 RTN 72 RCL 02 73 8 74 MOD 75 4 76 - 77 ABS 78 1 79 x=? Y 80 +/- 81 STO* 03 82 RTN 83 LBL 04 84 RCL 02 85 1 86 x≠? Y 87 CLx 88 RCL* 03 89 RTN 90 LBL 00 91 R↓ 92 ABS 93 1 94 x≠? Y 95 CLx 96 END I would be grateful for concrete suggestions for improvements & reports of any defects. RE: WP 34S Programme to solve Cornacchia's equation - Gerald H - 05-11-2014 10:49 AM Sorry, there were 2 typing errors in the programme KRN. Line 45 had "≠", corrected to "=" & line 86 had "=" corrected to "≠", these corrections having now been applied to the original post.