| Révision | 062b01da55e8349521f2d2cdbea3b103ff6ad82b (tree) |
|---|---|
| l'heure | 2022-10-16 01:52:58 |
| Auteur |  Simon Forman <sforman@hush...> |
| Commiter | Simon Forman |
That seems to work: addition and subtraction.
docs/notebooks/BigInts.ipynb (diff) implementations/bigints.joy (diff)| @@ -5078,39 +5078,245 @@ | ||
| 5078 | 5078 | ] |
| 5079 | 5079 | }, |
| 5080 | 5080 | { |
| 5081 | + "cell_type": "code", | |
| 5082 | + "execution_count": 211, | |
| 5083 | + "id": "3d29ed60", | |
| 5084 | + "metadata": {}, | |
| 5085 | + "outputs": [ | |
| 5086 | + { | |
| 5087 | + "name": "stdout", | |
| 5088 | + "output_type": "stream", | |
| 5089 | + "text": [] | |
| 5090 | + } | |
| 5091 | + ], | |
| 5092 | + "source": [ | |
| 5093 | + "clear" | |
| 5094 | + ] | |
| 5095 | + }, | |
| 5096 | + { | |
| 5097 | + "cell_type": "markdown", | |
| 5098 | + "id": "cb2fe4bb", | |
| 5099 | + "metadata": {}, | |
| 5100 | + "source": [ | |
| 5101 | + "#### `neg-bigint`" | |
| 5102 | + ] | |
| 5103 | + }, | |
| 5104 | + { | |
| 5105 | + "cell_type": "code", | |
| 5106 | + "execution_count": 212, | |
| 5107 | + "id": "47d10c16", | |
| 5108 | + "metadata": {}, | |
| 5109 | + "outputs": [ | |
| 5110 | + { | |
| 5111 | + "name": "stdout", | |
| 5112 | + "output_type": "stream", | |
| 5113 | + "text": [] | |
| 5114 | + } | |
| 5115 | + ], | |
| 5116 | + "source": [ | |
| 5117 | + "[neg-bigint [not] infra] inscribe" | |
| 5118 | + ] | |
| 5119 | + }, | |
| 5120 | + { | |
| 5121 | + "cell_type": "code", | |
| 5122 | + "execution_count": null, | |
| 5123 | + "id": "781a1ed2", | |
| 5124 | + "metadata": {}, | |
| 5125 | + "outputs": [], | |
| 5126 | + "source": [ | |
| 5127 | + "123 " | |
| 5128 | + ] | |
| 5129 | + }, | |
| 5130 | + { | |
| 5131 | + "cell_type": "code", | |
| 5132 | + "execution_count": 213, | |
| 5133 | + "id": "e2bf4564", | |
| 5134 | + "metadata": {}, | |
| 5135 | + "outputs": [ | |
| 5136 | + { | |
| 5137 | + "name": "stdout", | |
| 5138 | + "output_type": "stream", | |
| 5139 | + "text": [ | |
| 5140 | + "-123" | |
| 5141 | + ] | |
| 5142 | + } | |
| 5143 | + ], | |
| 5144 | + "source": [ | |
| 5145 | + "to-bigint neg-bigint from-bigint" | |
| 5146 | + ] | |
| 5147 | + }, | |
| 5148 | + { | |
| 5149 | + "cell_type": "code", | |
| 5150 | + "execution_count": 214, | |
| 5151 | + "id": "9b4c3ea7", | |
| 5152 | + "metadata": {}, | |
| 5153 | + "outputs": [ | |
| 5154 | + { | |
| 5155 | + "name": "stdout", | |
| 5156 | + "output_type": "stream", | |
| 5157 | + "text": [ | |
| 5158 | + "123" | |
| 5159 | + ] | |
| 5160 | + } | |
| 5161 | + ], | |
| 5162 | + "source": [ | |
| 5163 | + "to-bigint neg-bigint from-bigint" | |
| 5164 | + ] | |
| 5165 | + }, | |
| 5166 | + { | |
| 5167 | + "cell_type": "code", | |
| 5168 | + "execution_count": null, | |
| 5169 | + "id": "7c4edc9a", | |
| 5170 | + "metadata": {}, | |
| 5171 | + "outputs": [], | |
| 5172 | + "source": [] | |
| 5173 | + }, | |
| 5174 | + { | |
| 5175 | + "cell_type": "code", | |
| 5176 | + "execution_count": null, | |
| 5177 | + "id": "8d467543", | |
| 5178 | + "metadata": {}, | |
| 5179 | + "outputs": [], | |
| 5180 | + "source": [] | |
| 5181 | + }, | |
| 5182 | + { | |
| 5183 | + "cell_type": "code", | |
| 5184 | + "execution_count": null, | |
| 5185 | + "id": "5722d274", | |
| 5186 | + "metadata": {}, | |
| 5187 | + "outputs": [], | |
| 5188 | + "source": [] | |
| 5189 | + }, | |
| 5190 | + { | |
| 5191 | + "cell_type": "code", | |
| 5192 | + "execution_count": null, | |
| 5193 | + "id": "d08a5ea1", | |
| 5194 | + "metadata": {}, | |
| 5195 | + "outputs": [], | |
| 5196 | + "source": [] | |
| 5197 | + }, | |
| 5198 | + { | |
| 5199 | + "cell_type": "code", | |
| 5200 | + "execution_count": null, | |
| 5201 | + "id": "4e18e84a", | |
| 5202 | + "metadata": {}, | |
| 5203 | + "outputs": [], | |
| 5204 | + "source": [] | |
| 5205 | + }, | |
| 5206 | + { | |
| 5207 | + "cell_type": "code", | |
| 5208 | + "execution_count": null, | |
| 5209 | + "id": "b72d58e6", | |
| 5210 | + "metadata": {}, | |
| 5211 | + "outputs": [], | |
| 5212 | + "source": [] | |
| 5213 | + }, | |
| 5214 | + { | |
| 5215 | + "cell_type": "code", | |
| 5216 | + "execution_count": null, | |
| 5217 | + "id": "f134ab23", | |
| 5218 | + "metadata": {}, | |
| 5219 | + "outputs": [], | |
| 5220 | + "source": [] | |
| 5221 | + }, | |
| 5222 | + { | |
| 5081 | 5223 | "cell_type": "markdown", |
| 5082 | 5224 | "id": "f2b707c1", |
| 5083 | 5225 | "metadata": {}, |
| 5084 | 5226 | "source": [ |
| 5085 | 5227 | "## Appendix: Source Code\n", |
| 5228 | + " clear\n", | |
| 5229 | + " [base 2147483648]\n", | |
| 5230 | + " [ditch-empty-list [bool] [popd] [pop] ifte]\n", | |
| 5231 | + " [bool-to-int [0] [1] branch]\n", | |
| 5232 | + " [uncons-two [uncons] ii swapd]\n", | |
| 5233 | + " [sandwich swap [cons] dip swoncat]\n", | |
| 5234 | + "\n", | |
| 5235 | + " [digitalize [0 <=] [pop []] [base divmod swap] [i cons] genrec]\n", | |
| 5236 | + " [to-bigint [!-] [abs digitalize] cleave cons]\n", | |
| 5237 | + "\n", | |
| 5238 | + " [prep rest 1 0 rolldown]\n", | |
| 5239 | + " [from-bigint' [next-digit] step popd]\n", | |
| 5240 | + " [next-digit [increase-power] [accumulate-digit] clop popdd]\n", | |
| 5241 | + " [increase-power popop base *]\n", | |
| 5242 | + " [accumulate-digit rolldown * +]\n", | |
| 5243 | + "\n", | |
| 5244 | + " [sign-int [first] [prep from-bigint'] cleave]\n", | |
| 5245 | + " [neg-if-necessary swap [neg] [] branch]\n", | |
| 5246 | + " [from-bigint sign-int neg-if-necessary]\n", | |
| 5247 | + "\n", | |
| 5248 | + " [add-with-carry _add-with-carry0 _add-with-carry1]\n", | |
| 5249 | + " [_add-with-carry0 [bool-to-int] dipd + +]\n", | |
| 5250 | + " [_add-with-carry1 base [mod] [>=] clop]\n", | |
| 5251 | + "\n", | |
| 5252 | + " [add-carry-to-digits [pop not] [popd] [_actd_R0] [i cons] genrec]\n", | |
| 5253 | + " [_actd_R0 [bool] [_actd_R0.then] [_actd_R0.else] ifte]\n", | |
| 5254 | + " [_actd_R0.else popd 1 false rolldown]\n", | |
| 5255 | + " [_actd_R0.then 0 swap uncons [add-with-carry] dip]\n", | |
| 5256 | + "\n", | |
| 5257 | + " [add-digits initial-carry add-digits']\n", | |
| 5258 | + " [initial-carry false rollup]\n", | |
| 5259 | + "\n", | |
| 5260 | + " [add-digits' [P] [THEN] [R0] [R1] genrec]\n", | |
| 5261 | + " [P [bool] ii & not]\n", | |
| 5262 | + " [THEN [P'] [THEN'] [ELSE] ifte]\n", | |
| 5263 | + " [R0 uncons-two [add-with-carry] dipd]\n", | |
| 5264 | + " [R1 i cons]\n", | |
| 5265 | + " [P' [bool] ii |]\n", | |
| 5266 | + " [THEN' ditch-empty-list add-carry-to-digits]\n", | |
| 5267 | + " [ELSE pop swap [] [1 swons] branch]\n", | |
| 5268 | + "\n", | |
| 5269 | + " [same-sign [first] ii xor not]\n", | |
| 5270 | + " [add-like-bigints [uncons] dip rest add-digits cons]\n", | |
| 5271 | + " [add-bigints [same-sign] [add-like-bigints] [neg-bigint sub-like-bigints] ifte]\n", | |
| 5272 | + "\n", | |
| 5273 | + " [build-two-list-combiner _btlc0 _btlc1 [i cons]]\n", | |
| 5274 | + " [_btlc0.0 [[ditch-empty-list] swoncat] dip]\n", | |
| 5275 | + " [_btlc0.1 [pop] swoncat]\n", | |
| 5276 | + " [_btlc0.3 [_btlc0.0 _btlc0.1] dip]\n", | |
| 5277 | + " [_btlc0.4 [uncons-two] [dipd] sandwich]\n", | |
| 5278 | + " [_btlc0 _btlc0.3 _btlc0.4]\n", | |
| 5279 | + " [_btlc1 [[ifte] ccons [P'] swons [P] swap] dip]\n", | |
| 5280 | + "\n", | |
| 5281 | + " [carry [] [1 swons] branch]\n", | |
| 5282 | + "\n", | |
| 5283 | + " [compare-pairs [bool not] [pop false] [[first [>=] infrst] [pop true]] [[rest] swoncat ifte] genrec]\n", | |
| 5284 | + " [xR1 uncons-two [unit cons swons] dipd]\n", | |
| 5285 | + " [xP [bool] ii & not]\n", | |
| 5286 | + " [BASE [bool] [popop pop true] [[pop bool] [popop pop false] [popop compare-pairs] ifte] ifte]\n", | |
| 5287 | + " [gt-bigint <<{} [xP] [BASE] [xR1] tailrec]\n", | |
| 5288 | + " [check-gt [gt-bigint] [swap [not] dipd] [] ifte]\n", | |
| 5289 | + "\n", | |
| 5290 | + " [sub-carry pop]\n", | |
| 5291 | + "\n", | |
| 5292 | + " [sub-carry-from-digits [pop not] [popd] [_scfd_R0] [i cons-but-not-leading-zeroes] genrec] inscribe\n", | |
| 5293 | + " [_scfd_R0 uncons 0 swap [sub-with-carry] dip] inscribe\n", | |
| 5294 | + " [cons-but-not-leading-zeroes [P'] [cons] [popd] ifte]\n", | |
| 5295 | + "\n", | |
| 5296 | + " [sub-with-carry _sub-with-carry0 _sub-with-carry1]\n", | |
| 5297 | + " [_sub-with-carry0 rolldown bool-to-int [-] ii]\n", | |
| 5298 | + " [_sub-with-carry1 [base + base mod] [0 <] cleave]\n", | |
| 5299 | + "\n", | |
| 5300 | + " [sub-like-bigints [uncons] dip rest check-gt sub-digits cons]\n", | |
| 5301 | + " [sub-digits initial-carry sub-digits']\n", | |
| 5302 | + "\n", | |
| 5303 | + " enstacken [inscribe] step\n", | |
| 5304 | + "\n", | |
| 5305 | + " [add-carry-to-digits]\n", | |
| 5306 | + " [swap carry]\n", | |
| 5307 | + " [add-with-carry]\n", | |
| 5308 | + " build-two-list-combiner\n", | |
| 5309 | + " [genrec] ccons ccons\n", | |
| 5310 | + " [add-digits'] swoncat\n", | |
| 5311 | + " inscribe\n", | |
| 5086 | 5312 | "\n", |
| 5087 | - " base 2147483648\n", | |
| 5088 | - " ditch-empty-list [bool] [popd] [pop] ifte\n", | |
| 5089 | - " bool-to-int [0] [1] branch\n", | |
| 5090 | - " uncons-two [uncons] ii swapd\n", | |
| 5091 | - "\n", | |
| 5092 | - " add-with-carry _a0 _a1\n", | |
| 5093 | - " _a0 [bool-to-int] dipd + +\n", | |
| 5094 | - " _a1 base [mod] [>=] clop\n", | |
| 5095 | - "\n", | |
| 5096 | - " add-carry-to-digits [pop not] [popd] [_actd_R0] [i cons] genrec\n", | |
| 5097 | - " _actd_R0 [bool] [_actd_R0.then] [_actd_R0.else] ifte\n", | |
| 5098 | - " _actd_R0.else popd 1 false rolldown\n", | |
| 5099 | - " _actd_R0.then 0 swap uncons [add-with-carry] dip\n", | |
| 5100 | - "\n", | |
| 5101 | - " add-digits initial-carry add-digits'\n", | |
| 5102 | - " initial-carry false rollup\n", | |
| 5103 | - " add-digits' [P] [THEN] [R0] [i cons] genrec\n", | |
| 5104 | - " P [bool] ii & not\n", | |
| 5105 | - " THEN [P'] [THEN'] [ELSE] ifte\n", | |
| 5106 | - " R0 uncons-two [add-with-carry] dipd\n", | |
| 5107 | - " P' [bool] ii |\n", | |
| 5108 | - " THEN' ditch-empty-list add-carry-to-digits\n", | |
| 5109 | - " ELSE pop swap [] [1 swons] branch\n", | |
| 5110 | - "\n", | |
| 5111 | - " same-sign [first] ii xor not\n", | |
| 5112 | - " add-like-bigints [uncons] dip rest add-digits cons\n", | |
| 5113 | - " add-bigints [same-sign] [add-like-bigints] [1 0 /] ifte" | |
| 5313 | + " [sub-carry-from-digits]\n", | |
| 5314 | + " [swap sub-carry]\n", | |
| 5315 | + " [sub-with-carry]\n", | |
| 5316 | + " build-two-list-combiner\n", | |
| 5317 | + " [genrec] ccons ccons\n", | |
| 5318 | + " [sub-digits'] swoncat\n", | |
| 5319 | + " inscribe\n" | |
| 5114 | 5320 | ] |
| 5115 | 5321 | }, |
| 5116 | 5322 | { |
| @@ -5122,7 +5328,7 @@ | ||
| 5122 | 5328 | "\n", |
| 5123 | 5329 | "So far I have three formats for Joy source:\n", |
| 5124 | 5330 | "\n", |
| 5125 | - "- `def.txt` is a list of definitions (UTF-8), one per line, with no special marks (like above.)\n", | |
| 5331 | + "- `def.txt` is a list of definitions (UTF-8), one per line, with no special marks.\n", | |
| 5126 | 5332 | "- `foo ≡ bar baz...` lines in the `joy.py` embedded definition text, because why not? (Sometimes I use `==` instead of `≡` mostly because some tools can't handle the Unicode glyph. Like converting this notebook to PDF via LaTeX just omitted them.)\n", |
| 5127 | 5333 | "- `[name body] inscribe` Joy source code that literally defines new words in the dictionary at runtime. A text of those commands can be fed to the interpreter to customize it without any special processing (like the other two formats require.)\n", |
| 5128 | 5334 | "\n", |
| @@ -18,6 +18,8 @@ clear | ||
| 18 | 18 | [neg-if-necessary swap [neg] [] branch] |
| 19 | 19 | [from-bigint sign-int neg-if-necessary] |
| 20 | 20 | |
| 21 | +[neg-bigint [not] infra] | |
| 22 | + | |
| 21 | 23 | [add-with-carry _add-with-carry0 _add-with-carry1] |
| 22 | 24 | [_add-with-carry0 [bool-to-int] dipd + +] |
| 23 | 25 | [_add-with-carry1 base [mod] [>=] clop] |
| @@ -41,9 +43,9 @@ clear | ||
| 41 | 43 | |
| 42 | 44 | [same-sign [first] ii xor not] |
| 43 | 45 | [add-like-bigints [uncons] dip rest add-digits cons] |
| 44 | -[add-bigints [same-sign] [add-like-bigints] [1 0 /] ifte] | |
| 46 | +[add-bigints [same-sign] [add-like-bigints] [neg-bigint sub-like-bigints] ifte] | |
| 45 | 47 | |
| 46 | -[build-two-list-combiner _btlc0 _btlc1 [i cons]] | |
| 48 | +[build-two-list-combiner _btlc0 _btlc1 [[i cons] genrec] ccons cons] | |
| 47 | 49 | [_btlc0.0 [[ditch-empty-list] swoncat] dip] |
| 48 | 50 | [_btlc0.1 [pop] swoncat] |
| 49 | 51 | [_btlc0.3 [_btlc0.0 _btlc0.1] dip] |
| @@ -73,13 +75,14 @@ clear | ||
| 73 | 75 | [sub-like-bigints [uncons] dip rest check-gt sub-digits cons] |
| 74 | 76 | [sub-digits initial-carry sub-digits'] |
| 75 | 77 | |
| 78 | +[sub-bigints [same-sign] [sub-like-bigints] [neg-bigint add-like-bigints] ifte] | |
| 79 | + | |
| 76 | 80 | enstacken [inscribe] step |
| 77 | 81 | |
| 78 | 82 | [add-carry-to-digits] |
| 79 | 83 | [swap carry] |
| 80 | 84 | [add-with-carry] |
| 81 | 85 | build-two-list-combiner |
| 82 | -[genrec] ccons ccons | |
| 83 | 86 | [add-digits'] swoncat |
| 84 | 87 | inscribe |
| 85 | 88 |
| @@ -87,8 +90,5 @@ inscribe | ||
| 87 | 90 | [swap sub-carry] |
| 88 | 91 | [sub-with-carry] |
| 89 | 92 | build-two-list-combiner |
| 90 | -[genrec] ccons ccons | |
| 91 | 93 | [sub-digits'] swoncat |
| 92 | 94 | inscribe |
| 93 | - | |
| 94 | - |
Fork