8
\$\begingroup\$

Challenge

The cops created code challenges which result in certain wildly incorrect answers despite correct math. Choose an uncracked, not safe formula from the cop thread.

Your task is to find an incorrect answer and describe its underlying cause. The challenge author has the responsibility to confirm whether the explanation is valid, but the incorrect answer does not have to be the same one the challenge creator had in mind.

Scoring, Rules, and Notes

  • Score 1 point for each successfully cracked answer.
  • If the error is caused by a particular usage of an external library (or specific version of it), it is sufficient to simply state that there is a known bug with a particular usage of the library used by the cop challenge. Link to a relevant bug report or article.
    • This is to avoid having to pour through potentially millions of lines of source code in libraries (which may be closed source anyway) to find the exact cause of the error.

Example

Cop Challenge

  • Formula: The Pythagorean Theorem, \$ a^2 + b^2 = c^2 \$
  • Inputs: 2 nonnegative real numbers
  • Off by more than either input number
  • Affects most inputs
  • WSL (Ubuntu 18.04) on Windows 10, Python 3.6.9
def badpythag(a, b):
    a2 = (a / 1e200) ** 2
    b2 = (b / 1e200) ** 2
    return math.sqrt(a2 + b2) * 1e200

Cracked Answer

This will fail on many inputs (e.g. 3, 4 => 0, but should be 5) due to floating point underflow and return 0. The answer is correct with very large inputs e.g. 3e150 and 4e150, however.

\$\endgroup\$
8
\$\begingroup\$

Python 3 + Sympy, Sisyphus' Answer

from sympy.ntheory.primetest import mr
from sympy.ntheory.generate import primerange

def is_prime(n: int) -> bool:
	if n < 2: return False
	return mr(n, primerange(2, 800))

def is_prime_2(n: int) -> bool:
	if n < 2: return False
	return mr(n, [1009])

n = 2809386136371438866496346539320857607283794588353401165473007394921174159995576890097633348301878401799853448496604965862616291048652062065394646956750323263193037964463262192320342740843556773326129475220032687577421757298519461662249735906372935033549531355723541168448473213797808686850657266188854910604399375221284468243956369013816289853351613404802033369894673267294395882499368769744558478456847832293372532910707925159549055961870528474205973317584333504757691137280936247019772992086410290579840045352494329434008415453636962234340836064927449224611783307531275541463776950841504387756099277118377038405235871794332425052938384904092351280663156507379159650872073401637805282499411435158581593146712826943388219341340599170371727498381901415081480224172469034841153893464174362543356514320522139692755430021327765409775374978255770027259819794532960997484676733140078317807018465818200888425898964847614568913543667470861729894161917981606153150551439410460813448153180857197888310572079656577579695814664713878369660173739371415918888444922272634772987239224582905405240454751027613993535619787590841842251056960329294514093407010964283471430374834873427180817297408975879673867

print(is_prime(n))    # Prints True
print(is_prime_2(n))  # Prints False

Try it online!

n is strongly pseudoprime for all prime bases below 1,000, which means the Miller-Rabin test will give a false positive for any bases in the (2, 800) range. As soon as you use a prime base above 1,000, the Miller-Rabin test correctly identifies it as composite.

I did not calculate this number myself. I took it from this answer from Joe53 on Mathematics Stack Exchange, which in turn was calculated using the technique in this paper.

\$\endgroup\$
1
  • \$\begingroup\$ Very nice! I didn't generate the prime either, but took it from the Prime and Prejudice paper. \$\endgroup\$
    – Sisyphus
    Jan 15 at 10:02
2
\$\begingroup\$

JavaScript (Node.js), tsh's answer

function max(a, b) {
  if (typeof a !== 'number' || typeof b !== 'number') {
    throw TypeError("This function only accept numbers");
  }
  if (a === b) {
    return a;
  } else if (a > b) {
    return a;
  } else if (a < b) {
    return b;
  } else {
    return Math.max(a, b);
  }
}

function max_ref(a, b) {
  if (typeof a !== 'number' || typeof b !== 'number') {
    throw TypeError("This function only accept numbers");
  }
  return Math.max(a, b);
}

console.log(max(-0, 0));
console.log(max_ref(-0, 0));

Try it online!

-0
0

According to ===, signed 0 is equal to unsigned 0, but as shown in this SO post, Math.max has a special case for signed 0.

The first argument is returned when the === is true, so all we have to do is call it with -0, 0 for it to return the wrong answer.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Damnit! I was seconds away!! \$\endgroup\$
    – pxeger
    Jan 16 at 15:40
2
\$\begingroup\$

Lua (LuaJIT), cracks @LuaNoob's answer

function Fails(i)
    local max = i * 80
    local a = 0

    while true do
        if a < max then
            a = a + 0.2
        else
            break
        end
    end

    print("Input", i)
    print("Max", max)
    print("Expected Value", string.format("%.64f", max))
    print("Value", string.format("%.64f", a))
    print("Value-0.2", string.format("%.64f", a-0.2))
    print("Equal?", a == max)
    print()
end

Fails(0.46) -- fails
Fails(0.47) -- works

Try it online!

Works with 0.47 (found by trial and error). No doubt many other values also produce the 'expected' answer.

With the slightly modified code above we see that the failure for some inputs is due to floating point errors. Specifically, repeated addition (a + 0.2) is not the same as multiplication (i * 80) in floating point arithmetic. Compensated summation algorithms, such as Kahan summation, are designed to reduce precision loss due to repeated addition.

\$\endgroup\$
1
  • \$\begingroup\$ Nice, I just tried to run a for loop for the input 0, 1, 0.01 and the results of the loop as input are wrong if you put them inside the func manually. \$\endgroup\$
    – LuaNoob
    Jan 17 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.