2 replies to this topic

[The Crazy Phoenix]

I'm writing an API that revolves around mathematics. Within this API, I have basic arithmetic operations that receive multiple arguments and apply the operation with each argument, where the first argument is the value on which to apply the operation.

So for example, I would have divide(n, a, and it would do n / a followed by n / b (it's actually simplified to n / (a * if a * b is found to not exceed the bit32 limit).

I'd like to write a similar function for modulo but I can't think of a proper way of simplifying multiple operands to optimize the algorithm.
Here are the ideas I currently have, given that the additional arguments are numbered alphabetically.

• If b > a then skip b because n mod a mod b = n mod a
  
• If b | a then skip a because n mod a mod b = n mod b
  
• If n mod a is 0 then skip all following moduli

I'm ideally looking for a rule that can simplify all additional arguments into a single value no matter what their value is. If that's not possible, I'm looking to simplify it to the least arguments.

[Bomb Bloke]

You'd filter out more pointless args by checking "curArg > lastOutput", rather than "curArg > allPreviousArgs" (which also would've been better phrased as "curArg >= allPreviousArgs"). Though I rather suspect it'd be faster to skip the comparison completely and just run the modulus operation on everything.

"b | a" may also lead to more processing overall. Consider mod(303, 100, 2) - if you skip the 100 arg, then the system has to count through 151 two's to get the answer. If you process it normally, it has to count three hundreds, and then one two.

Long story short I suspect the fastest execution you'll get is to simply process all args, no matter what they are, until you either run out or get a result of 0.

[The Crazy Phoenix]

Bomb Bloke, on 14 July 2016 - 11:31 AM, said:

You'd filter out more pointless args by checking "curArg > lastOutput", rather than "curArg > allPreviousArgs" (which also would've been better phrased as "curArg >= allPreviousArgs").

I was already planning on doing that.

Bomb Bloke, on 14 July 2016 - 11:31 AM, said:

Though I rather suspect it'd be faster to skip the comparison completely and just run the modulus operation on everything.

Modulus involves floored division, so I'd rather skip as many as I can skip as division of larger numbers can be quite intensive, especially when you reach 2^200 (API is not bound to number's limitations).

Bomb Bloke, on 14 July 2016 - 11:31 AM, said:

"b | a" may also lead to more processing overall.

That is why I was asking for an optimization that would ideally run no matter what the number is.