Trans-compiling Python aks primality test to JavaScript

Question

I am trans-compiling this Python code:

def expand_x_1(p):
    ex = [1]
    for i in range(p):
        ex.append(ex[-1] * -(p-i) / (i+1))
    return ex[::-1]
def aks_test(p):
    if p < 2: return False
    ex = expand_x_1(p)
    ex[0] += 1
    return not any(mult % p for mult in ex[0:-1])
for p in range(101):
    if aks_test(p):
        print(p)

Into JavaScript. Here is what I have done so far:

function expand_x_1(p){
    var ex = [1];
    for(i = 0; i < p; i++){
        ex.push(ex[ex.length - 2] * -(p-i) / (i+1));
    }
    return ex.reverse();
}
function aks_test(p){
    if(p < 2)
        return false;
    var ex = expand_x_1(p);
    ex[0] += 1;
    // the return part right here is what I need help with.
}
// Python equivalent of any()
function any(iterable){
    for(element in iterable)
        if(element)
            return true;
    return false;
}

I just need help converting this line of Python code into JavaScript:

return not any(mult % p for mult in ex[0:-1])

Thanks!

score 0 · Answer 1 · answered Apr 22 '14 at 01:11

0

Your JavaScript implementation of any will not work with Arrays. You better be using Array.prototype.some (and Array.prototype.every for Python's all).

Since we don't have generator expressions, in JavaScript, you can do

return ex.slice(0, -1).some(function(currentItem) {
    currentItem % p;
});

We slice the array, so we can exclude the last element.

answered Apr 22 '14 at 01:11

thefourtheye

233,700
52
457
497

Hmm, my script still isn't working correctly even when I try your suggestion. – Progo Apr 22 '14 at 01:15
Be aware that in JavaScript, the `%` operator is not a true modulo. It will only work as Python's does for positive numbers. See [this question](http://stackoverflow.com/questions/4467539/javascript-modulo-not-behaving) to help solve that issue. – jshanley Apr 22 '14 at 01:19
@jshanley I tried implementing your suggestion but it still doesn't work… – Progo Apr 22 '14 at 01:21
@Progo not working correctly, doesn't give me any clues – thefourtheye Apr 22 '14 at 01:59
@Progo Sorry, I have no idea about AKS testing algorithm – thefourtheye Apr 22 '14 at 05:57

score 0 · Answer 2 · edited May 23 '17 at 10:26

First, define a modulo function to make sure the modulo behaves the same way as in Python:

function modulo(a, b) {
    return ((a % b) + b) % b;
}

The 'not any' line really just means that you want to return true if none of the iterations of the modulo get a result of 0. You can't do a list comprehension in JS, but you can get the same result by doing something like this.

// just use length-1 instead of slicing array
for (var i = 0; i < ex.length - 1; i++) {
  var mult = ex[i];
  // modulo mult by p
  var test = modulo(mult, p);
  // return false if any modulo result is 0
  if (test === 0) {
    return false;
  }
}
// will only make it this far if all modulos !== 0
return true;

--EDIT--

I only expanded it to make it easier to follow, you could make the for-loop much simpler:

for (var i = 0; i < ex.length - 1; i++) {
  if (modulo(ex[i], p) === 0) {
    return false;
  }
}
return true;

I tried implementing your suggestion, but now it is just behaving strangely: http://jsfiddle.net/Progo/aqN94/ — Progo, Apr 22 '14 at 12:31

Trans-compiling Python aks primality test to JavaScript

2 Answers2