def jacobi(a, b):
    """Calculates the value of the Jacobi symbol (a/b) where both a and b are
    positive integers, and b is odd

    :returns: -1, 0 or 1
    """
    assert a > 0
    assert b > 0
    if a == 0:
        return 0
    result = 1
    while a > 1:
        if a & 1:
            if (a - 1) * (b - 1) >> 2 & 1:
                result = -result
            a, b = b % a, a
        else:
            if b * b - 1 >> 3 & 1:
                result = -result
            a >>= 1
    if a == 0:
        return 0
    return result
