Problem 145 in JavaScript

grey2010 2019-10-02 18:25:19

Has anyone solved this on javascript? Hi everyone! This task turned out to be a tough nut. A little more and I will begin to write a scientific paper on the behavior of modulo exponentiation algorithms. And they behave very strange. Now the bottom line: we have 4 algorithms collected from the back streets of the Internet. These ones:

/1. Here the value of degree is represented as a binary number and the right-to-left scheme presented on Wikipedia is used./

    const PowToModFromWiki = (base, pow, mod) =>{
            let step = pow.toString(2).split('').map(Number);
            let result = 1;
            for(let i=step.length-1;i>0;i--){
                  result =(result * base**step[i])%mod;
                  base = (base**2)%mod;
            }
            return (result*base)%mod;
        }

/* 2. Here we square the base and simplify the value of the degree.*/

        const anotherPowToMod = (base, pow, mod) => {
            let temp = 1;
            while (pow>0){
                if (!(pow%2)) {
                    base = (base**2)%mod;
                    pow/=2;
                }
                else {
                    pow--;
                    temp =(temp * base)%mod;
                }
            }
            return temp;
        }

/3. Here's a popular binary exponentiation algorithm/

        const recursePowToMod = (base, pow, mod) => {
            const bynPow = (base, pow) =>{
                if (pow == 1) return base; 
                if (pow%2 == 0) {
                let temp = bynPow(base, pow/2);
                return temp**2%mod;
                    } else return bynPow(base, pow-1)*base%mod;
            }
            return bynPow (base, pow);
        }

/4. This is the simplest (school) algorithm. It returns the largest number of correct results, but also breaks./

        const tooDumbPowToMod = (base, pow, mod) => {
            let result = 1;
            for(let i=0; i<pow; i++) {
                result = result * base % mod;
            }
            return result;
        }

For small values of base, degree, and module, they return the same correct values. But then, with the growth of these values, they begin to diverge. By running them in a loop, I found out that the returned values are identical if the module value is about 760,000,000, and if the base value is odd, then the module is even smaller - about 950,000,000. The value of the base and value of degree (even though my cycle has not reached even large numbers) at speed "breakdowns" do not affect. Obviously (probably) that these miracles are somehow related to the representation of numbers in js ...? If site rules allow it, give me a hint: what am I doing wrong? Otherwise, I will have to continue my scientific research and I'm afraid it will drag on for a long time.

grey2010 2019-10-02 18:27:44

Strange formatted code....Yeah, I fixed it.

Rodion (admin) 2019-10-03 05:05:10

Hi Friend!

these miracles are somehow related to the representation of numbers in js ...?

I'm not JS guru, but you may notice that JS usually does silent conversion of types - I would call it "weak-typing", just as in PHP, though JS proponents hate when JS is called so (and hate comparison with PHP). They prefer word "untyped" which really is definitely incorrect, as we have "typeof" operator :)

You may found that up to certain value JS uses either integers or float values with precise integer part, e.g.:

Math.pow(2,50)+1 = 1125899906842625      // odd number, correct
Math.pow(2,60)+1 = 1152921504606847000   // not odd... loss of precision, ha-ha-ha

I.e. think of it that when numbers become large enough, they are represented as non-precise values in "floating point" format. Of course this won't do for calculation of modulo:

Math.pow(3,40) % 2 == 0   // WAT? all powers of 3 should be odd...

googling says we have Number.MAX_SAFE_INTEGER constant...

For this problem you need to be sure that at every step intermediate results are correct, i.e. fall below this limit, however...

As value of A in this task may be up to 9 decimal digits, even raising it to power of 2 may give you imprecise value (slightly larger than this MAX_SAFE_INTEGER).

This means if you want to solve this in JavaScript, you need either:

to implement long arithmetics manually (e.g. represent numbers as strings or arrays)
or find suitable library

A little more and I will begin to write a scientific paper

...or studying documentation, joke :)

grey2010 2019-10-17 18:48:09

Rodion, thanks for the answer. After a couple of weeks of researching accuracy in js, I found out that it not only does not know how to multiply, divide, etc., but even convert the string to a number! Having written a couple of algorithms for multiplying and subtracting numbers in a string representation, I solved the problem. Perhaps this will help someone in the future who does not want to use third-party libraries and node.js

Please login and solve 5 problems to be able to post at forum