难逢只有0回报(Stumped on Just 0 return)

难逢只有0回报(Stumped on Just 0 return)

好的，稍微编辑一下，例如encode 99 18 108 45 = Nothing是真正正确的，显然我不能正确阅读问题，因为99和18不是素数，所以我在代码中添加了一个检查函数：

coprime :: Int -> Int -> Bool coprime a b = gcd a b == 1 check :: Int -> Int -> Bool check p q = (isPrime p) && (isPrime q) phi :: Int -> Int -> Int phi p q = (p - 1) * (q - 1) encrypt :: Int -> Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q) encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

这一次我的问题似乎是encode 53 73 151 90 = Just 133但例子说它应该返回Just 3869而不是Just 133 。

所以我向你们提出的问题是：我只是一个白痴，没有看到我面前的错误，或者我的工作正常吗？

如果你想要，我会把isPrime代码提起来，但是它只是检查一个不是。 通过返回true或false来表示是否为素数。

Ok, slight edit as the example encode 99 18 108 45 = Nothing was actually correct and apparently I can't read questions properly, as 99 and 18 aren't prime, so I added a check funct into the code:

coprime :: Int -> Int -> Bool coprime a b = gcd a b == 1 check :: Int -> Int -> Bool check p q = (isPrime p) && (isPrime q) phi :: Int -> Int -> Int phi p q = (p - 1) * (q - 1) encrypt :: Int -> Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q) encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

This time around my problem seems to be encode 53 73 151 90 = Just 133 but the example says it should return Just 3869 rather than Just 133.

So my question to you guys is: am I just being an idiot and not seeing the fault right in front of me or is my working ok?

I'll put isPrime code up if you want as well, however it just checks whether a no. is prime or not by returning true or false.

最满意答案

你的问题是你将数字提高到一个很大的数字，而这个数字非常大，而Int通常包含最多64位的数字。 结果，我们得到溢出，CPU将执行环绕。

通过直接计算公式来计算^b mod c通常不是一个好主意。 我们可以在这里使用更聪明的方法：因为（a×b） mod c ==（（a mod c）×（b mod c）） mod c ，我们可以通过以我们需要的方式计算功率来利用这个属性最少量的内存：

powmod :: Int -> Int -> Int -> Int powmod _ 0 _ = 1 powmod a b c | even b = ab2 | otherwise = mod (a * ab2) c where ab2 = powmod (mod (a * a) c) (div b 2) c

所以在这里我们计算O（log b） （其中b的值为功率） a ^b mod c ，其中^b本身可以通过在所有递归级别执行模运算而变得非常大。 我们在这里假设c小于Int的最大值的平方根。 由于一个Int至少有一个最小上界2 ²⁹ -1 ，这意味着它的工作时间长达c≤23'170。 如果你需要一个可以处理更高值的函数，那么你最好使用Int64 （ c最大值是3'037'000'499）或Integer （任意最大值）。

现在我们可以将这个函数用于encrypt函数：

encrypt :: Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q)

但是，您的encode功能可以改进。 您使用== True ，这是不必要的，因为True == True为True ， False == True为False 。

encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

现在我们得到：

Prelude> encode 99 18 108 45 Just 1134 Prelude> encode 37 17 23 48 Nothing

Your problem is that you raise numbers to a large power, which results in very large numbers, and Int usually contains up to 64-bit numbers. As a result, we get overflow, and the CPU will perform a wrap around.

It is usually not a good idea to calcuate a^b mod c by calculating the formula directly. We can use a more clever approach here: since (a×b) mod c == ((a mod c) × (b mod c)) mod c, we can exploit this property by calculating the power in such way that we require a minimal amount of memory:

powmod :: Int -> Int -> Int -> Int powmod _ 0 _ = 1 powmod a b c | even b = ab2 | otherwise = mod (a * ab2) c where ab2 = powmod (mod (a * a) c) (div b 2) c

So here we calculate in O(log b) (with b the value the power) a^b mod c, where a^b itself can be very large by performing modulo operations at all recursion levels. We here make the assumption that c is smaller than the square root of the maximum value of Int. Since an Int at least has a minimum upper bound of 2²⁹-1, this means that it works as long as c ≤ 23'170. In case you need a function that works with higher values, then you better use Int64 (max value for c is 3'037'000'499) or Integer (arbitrary maximum value).

Now we can use this function for the encrypt function:

encrypt :: Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q)

Your encode function can however be improved. You use == True, which is unnecessary, since True == True is True, and False == True is False.

encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

Now we get:

Prelude> encode 99 18 108 45 Just 1134 Prelude> encode 37 17 23 48 Nothing难逢只有0回报(Stumped on Just 0 return)

好的，稍微编辑一下，例如encode 99 18 108 45 = Nothing是真正正确的，显然我不能正确阅读问题，因为99和18不是素数，所以我在代码中添加了一个检查函数：

coprime :: Int -> Int -> Bool coprime a b = gcd a b == 1 check :: Int -> Int -> Bool check p q = (isPrime p) && (isPrime q) phi :: Int -> Int -> Int phi p q = (p - 1) * (q - 1) encrypt :: Int -> Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q) encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

这一次我的问题似乎是encode 53 73 151 90 = Just 133但例子说它应该返回Just 3869而不是Just 133 。

所以我向你们提出的问题是：我只是一个白痴，没有看到我面前的错误，或者我的工作正常吗？

如果你想要，我会把isPrime代码提起来，但是它只是检查一个不是。 通过返回true或false来表示是否为素数。

Ok, slight edit as the example encode 99 18 108 45 = Nothing was actually correct and apparently I can't read questions properly, as 99 and 18 aren't prime, so I added a check funct into the code:

coprime :: Int -> Int -> Bool coprime a b = gcd a b == 1 check :: Int -> Int -> Bool check p q = (isPrime p) && (isPrime q) phi :: Int -> Int -> Int phi p q = (p - 1) * (q - 1) encrypt :: Int -> Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q) encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

This time around my problem seems to be encode 53 73 151 90 = Just 133 but the example says it should return Just 3869 rather than Just 133.

So my question to you guys is: am I just being an idiot and not seeing the fault right in front of me or is my working ok?

I'll put isPrime code up if you want as well, however it just checks whether a no. is prime or not by returning true or false.

最满意答案

你的问题是你将数字提高到一个很大的数字，而这个数字非常大，而Int通常包含最多64位的数字。 结果，我们得到溢出，CPU将执行环绕。

通过直接计算公式来计算^b mod c通常不是一个好主意。 我们可以在这里使用更聪明的方法：因为（a×b） mod c ==（（a mod c）×（b mod c）） mod c ，我们可以通过以我们需要的方式计算功率来利用这个属性最少量的内存：

powmod :: Int -> Int -> Int -> Int powmod _ 0 _ = 1 powmod a b c | even b = ab2 | otherwise = mod (a * ab2) c where ab2 = powmod (mod (a * a) c) (div b 2) c

所以在这里我们计算O（log b） （其中b的值为功率） a ^b mod c ，其中^b本身可以通过在所有递归级别执行模运算而变得非常大。 我们在这里假设c小于Int的最大值的平方根。 由于一个Int至少有一个最小上界2 ²⁹ -1 ，这意味着它的工作时间长达c≤23'170。 如果你需要一个可以处理更高值的函数，那么你最好使用Int64 （ c最大值是3'037'000'499）或Integer （任意最大值）。

现在我们可以将这个函数用于encrypt函数：

encrypt :: Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q)

但是，您的encode功能可以改进。 您使用== True ，这是不必要的，因为True == True为True ， False == True为False 。

encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

现在我们得到：

Prelude> encode 99 18 108 45 Just 1134 Prelude> encode 37 17 23 48 Nothing

Your problem is that you raise numbers to a large power, which results in very large numbers, and Int usually contains up to 64-bit numbers. As a result, we get overflow, and the CPU will perform a wrap around.

It is usually not a good idea to calcuate a^b mod c by calculating the formula directly. We can use a more clever approach here: since (a×b) mod c == ((a mod c) × (b mod c)) mod c, we can exploit this property by calculating the power in such way that we require a minimal amount of memory:

powmod :: Int -> Int -> Int -> Int powmod _ 0 _ = 1 powmod a b c | even b = ab2 | otherwise = mod (a * ab2) c where ab2 = powmod (mod (a * a) c) (div b 2) c

So here we calculate in O(log b) (with b the value the power) a^b mod c, where a^b itself can be very large by performing modulo operations at all recursion levels. We here make the assumption that c is smaller than the square root of the maximum value of Int. Since an Int at least has a minimum upper bound of 2²⁹-1, this means that it works as long as c ≤ 23'170. In case you need a function that works with higher values, then you better use Int64 (max value for c is 3'037'000'499) or Integer (arbitrary maximum value).

Now we can use this function for the encrypt function:

encrypt :: Int -> Int -> Int -> Int encrypt p q m e = powmod m e (p * q)

Your encode function can however be improved. You use == True, which is unnecessary, since True == True is True, and False == True is False.

encode :: Int -> Int -> Int -> Int -> Maybe Int encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e) |otherwise = Nothing

Now we get:

Prelude> encode 99 18 108 45 Just 1134 Prelude> encode 37 17 23 48 Nothing