search

Doenet / DoenetML

Semantic markup for building interactive web activities
https://www.doenet.org/
GNU Affero General Public License v3.0
3 stars 16 forks source link

Create modular multiplicative inverse and exponentiation components #141

Open rogness opened 5 months ago

rogness commented 5 months ago

We have the <mod> component, which calls the mod command from math.js. In DoenetML,

<mod>8 3</mod>

is mapped (I presume?) to math.mod(8,3) in math.js, and returns 1.

This request is implement the `math.invmod(a,b)' command in DoenetML as well. The component

<invmod>7 13</invmod>

would call math.invmod(7,13) and return 2.

(I don't have strong feelings about whether the component is named <invmod> or <modinv> or something else. -- I used <invmod> above for consistency with math.js.)

rogness commented 5 months ago

...and while I'm asking, it would be really helpful to have fast modular exponentiation implemented. That's slightly more involved, because (surprisingly?) it doesn't exist in math.js. However, there are short javascript implementations of various algorithms all over the place, e.g.

https://stackoverflow.com/questions/66459806/javascript-number-too-big-for-modulo

https://umaranis.com/2018/07/12/calculate-modular-exponentiation-powermod-in-javascript-ap-n/

Following the syntax of the <mod> component, I'd imagine something like <PowerMod>999 17 23</PowerMod> to compute 999^17 % 23. (Theoretically I suppose the exponent and modulus could be defined via attributes or children, as well, but that would be a shift from the existing syntax?)