2c:null 2d:["$","title",null,{"children":"Prosthaphaeresis | Ryan Govostes | Observable"}] 32:[] 30:{"id":"5b8d0748ca90da94","slug":"prosthaphaeresis","title":"Prosthaphaeresis","thumbnail":"73facb9bc4388636e0335ddb72641198595220a3b4ba6d5e06b3e986e5386af1","access_level":"public","create_time":"$D2020-11-20T03:43:07.132Z","update_time":"$D2020-11-20T06:02:19.468Z","view_time":null,"first_public_time":"$D2020-11-20T05:28:03.982Z","has_unpublished_edits":null,"fork":false,"stars":6,"starred":false,"owner":{"type":"team","id":"65df3ecf4cd34ba4","login":"rzg","name":"Ryan Govostes","avatar_url":"https://avatars-next.observableusercontent.com/21d7729173c52aa42247b8005b8a3b3f51f85d9a293c62a6c90b23d343cdae78","tier":"starter_2024"},"version":354,"publish_version":354,"role":null,"authored":false,"authors":[{"type":"individual","id":"330de37f631825b8","login":"rzg","name":"Ryan Govostes","avatar_url":"https://avatars-next.observableusercontent.com/21d7729173c52aa42247b8005b8a3b3f51f85d9a293c62a6c90b23d343cdae78","tier":null}],"members":[{"type":"individual","id":"330de37f631825b8","login":"rzg","name":"Ryan Govostes","avatar_url":"https://avatars-next.observableusercontent.com/21d7729173c52aa42247b8005b8a3b3f51f85d9a293c62a6c90b23d343cdae78","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Prosthaphaeresis","cells":[{"id":0,"value":"md`\n# Prosthaphaeresis\n\n[Prosthaphaeresis][wikipedia] is an algorithm for quickly approximating products of large numbers using trigonometric identities, in use from the late 16th century until the logarithm was discovered in 1614.\n\n[wikipedia]: https://en.wikipedia.org/wiki/Prosthaphaeresis\n\nUsing the identity ${tex.block`\\cos{\\alpha} \\cos{\\beta} = \\frac{\\cos\\left(\\alpha - \\beta\\right) + \\cos\\left(\\alpha + \\beta\\right)}{2},`} and pre-computed lookup tables of cosines, it is possible to perform multiplication using the simpler operations of addition, subtraction, and finding the midpoint between two values.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"tex`a:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"viewof a = number({value: 3754})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"tex`b:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"viewof b = number({value: 1538})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":307,"value":"md`\nThe prosthaphaeresis algorithm gives us an approximation of ${tex.block`ab = \\left(${a}\\right)\\left(${b}\\right) \\approx ${approximation}.`}\n\nThe true value is ${tex`${a*b}`}, so our approximation is within ${tex`${round(100 * Math.abs((approximation - a*b) / (a*b)), 2) || 0}\\%`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":310,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"md`\nFirst we need to transform the product that we want to approximate, ${tex`ab`}, to fit the form ${tex`\\cos{\\alpha}\\cos{\\beta}`} so that we can use this identity.\n\nWe do so by scaling ${tex`a`} and ${tex`b`} into the ${tex`-1`} to ${tex`1`} range of the cosine function. Simply shifting the decimal point will do, as long as we remember to undo this at the end. Call these shifted inputs ${tex`\\cos{\\alpha}`} and ${tex`\\cos{\\beta}`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"tex.block`\n\\begin{aligned}\n\\cos{\\alpha} &= ${a} / {10}^{${one.ashift}} = ${one.cosalpha} \\\\\n\\cos{\\beta} &= ${b} / {10}^{${one.bshift}} = ${one.cosbeta}\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"md`\nNow we can look up in our table the angles ${tex`\\alpha`} and ${tex`\\beta`} from their cosines.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"html`\n\n\n \n\n \n\n \n\n \n\n \n

${tex`\\alpha`}	${tex`\\cos{\\alpha}`}	\n	${tex`\\beta`}	${tex`\\cos{\\beta}`}
${round(two.alpha - 0.001, 4)}	${round(Math.cos(two.alpha - 0.001), 4)}	\n	${round(two.beta - 0.001, 4)}	${round(Math.cos(two.beta - 0.001), 4)}	\n
${two.alpha}	${round(Math.cos(two.alpha), 4)}	\n	${two.beta}	${round(Math.cos(two.beta), 4)}	\n
${round(two.alpha + 0.001, 4)}	${round(Math.cos(two.alpha + 0.001), 4)}	\n	${round(two.beta + 0.001, 4)}	${round(Math.cos(two.beta + 0.001), 4)}	\n
...	...	\n	...	...	\n

${tex`\\alpha - \\beta`}	${tex`\\cos\\left(\\alpha - \\beta\\right)`}	\n	${tex`\\alpha + \\beta`}	${tex`\\cos\\left(\\alpha + \\beta\\right)`}	\n
${round(three.alphaminusbeta - 0.001, 4)}	${round(Math.cos(three.alphaminusbeta - 0.001), 4)}	\n	${round(three.alphaplusbeta - 0.001, 4)}	${round(Math.cos(three.alphaplusbeta - 0.001), 4)}	\n
${three.alphaminusbeta}	${round(Math.cos(three.alphaminusbeta), 4)}	\n	${three.alphaplusbeta}	${round(Math.cos(three.alphaplusbeta), 4)}	\n
${round(three.alphaminusbeta + 0.001, 4)}	${round(Math.cos(three.alphaminusbeta + 0.001), 4)}	\n	${round(three.alphaplusbeta + 0.001, 4)}	${round(Math.cos(three.alphaplusbeta + 0.001), 4)}	\n
...	...	\n	...	...	\n

\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"md`\nThe remaining sum and division by ${tex`2`} operations require us to find the midpoint between these values, resulting in\n\n${tex.block`\n\\cos{\\alpha} \\cos{\\beta} = \\left(${a} / {10}^{${one.ashift}}\\right)\\left(${b} / {10}^{${one.bshift}}\\right) \\approx ${three.midpoint}.\n`}\n\n\nFinally, we reverse the initial process of shifting the decimal point a total of ${one.ashift + one.bshift} places.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"import {number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"// from http://www.jacklmoore.com/notes/rounding-in-javascript/\nfunction round(value, decimals) {\n return Number(Math.round(value+'e'+decimals)+'e-'+decimals);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"one = {\n var cosalpha = a, cosbeta = b;\n var ashift = 0, bshift = 0;\n while (cosalpha < -1 || cosalpha > 1) { cosalpha /= 10; ashift ++; }\n while (cosbeta < -1 || cosbeta > 1) { cosbeta /= 10; bshift ++; }\n return {\n cosalpha: round(cosalpha, 4),\n cosbeta: round(cosbeta, 4),\n ashift: ashift,\n bshift: bshift\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"two = {\n return {\n alpha: round(Math.acos(one.cosalpha), 4),\n beta: round(Math.acos(one.cosbeta), 4),\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"three = {\n var alphaplusbeta = round(two.alpha + two.beta, 4);\n var alphaminusbeta = round(two.alpha - two.beta, 4);\n return {\n alphaplusbeta: alphaplusbeta,\n alphaminusbeta: alphaminusbeta,\n cosalphaplusbeta: round(Math.cos(alphaplusbeta), 4),\n cosalphaminusbeta: round(Math.cos(alphaplusbeta), 4),\n midpoint: round((Math.cos(alphaplusbeta) + Math.cos(alphaminusbeta)) / 2, 4)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":230,"value":"approximation = round(three.midpoint * Math.pow(10, one.ashift) * Math.pow(10, one.bshift), 0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1"}} 31:"$30:body"