用 Python 编写的求最小公倍数算法中的奇怪错误

Question

出于教育目的，我正在尝试构建一种有效的算法来查找最小公倍数。我已经有一个二次和缓慢的实现。我正在尝试建立一个新的。我的新实现使用涉及最大公约数 (GCD) 和最小公倍数 (LCM) 的数学属性。

基本上：对于任意两个正整数a和b，

LCM(a, b) * GCD(a, b) = a * b

我为此使用 Python 3。

我有一个非常有效的 GCD 实现（它使用了另一个数学属性，但谈论那个毫无意义）：

def euclidean_gcd(a,b):
    if b == 0:
        return a
    else:
        a_prime = a%b
        return euclidean_gcd(b,a_prime)

我的 LCM 实现是：

def lcm_fast(a,b):
    return (int((a*b)/(euclidean_gcd(a,b))))

然而，当我打电话时：

lcm_fast(1023473145,226553150)

我得到的输出是：

46374212988031352

正确答案应该是一个接近的数字：

46374212988031350

我是初学者（应用数学专业二年级），为什么会这样？

我不确定我是否掌握了整数溢出的概念，但是根据我所做的一些研究的理解，Python中没有整数溢出。

我做了压力测试，试图在一个更容易理解的案例中找到这个错误。然而，这个问题似乎只发生在非常大的数字上。您可以在下面检查我的压力测试：

import random

#defina a fronteira máxima dos testes randômicos

print ("insira um número para ser o final do intervalo de testes aleatórios")
bound_right = int(input())

#versão lenta, ou naive

def check_elem_in_list(list_1,list_2):
    for element in list_1:
        if element in list_2:
            return element
    else:
        return False

#nested loops, vai ter comportamento quadrático

def lcm_slow(num_1,num_2):

    list_of_num_1_prod = []
    list_of_num_2_prod = []
    max_nums = max(num_1,num_2)
    end_range = max_nums +1
    for i in range(1, end_range):
        list_of_num_1_prod.append(i*num_1)
        list_of_num_2_prod.append(i*num_2)
        if check_elem_in_list(list_of_num_1_prod,list_of_num_2_prod) != False:
            return (check_elem_in_list(list_of_num_1_prod,list_of_num_2_prod))

def euclidean_gcd(a,b):
    if b == 0:
        return a
    else:
        a_prime = a%b
        return euclidean_gcd(b,a_prime)

def lcm_fast(a,b):
    return (int((a*b)/(euclidean_gcd(a,b))))


# está dando pau com os inputs 1023473145, 226553150
# vou fazer stress testing
#primeiro, fazer função para gerar testes

a_in = random.randint(1,bound_right)
b_in = random.randint(1,bound_right)


while (lcm_slow(a_in,b_in)==lcm_fast(a_in,b_in)):
    a_in = random.randint(1,bound_right)
    b_in = random.randint(1,bound_right)
    print (a_in,b_in,"OK",lcm_fast(a_in,b_in),lcm_slow(a_in,b_in))
    if (lcm_slow(a_in,b_in)!=lcm_fast(a_in,b_in)):
        print (a_in, b_in,"OPS",lcm_fast(a_in,b_in),lcm_slow(a_in,b_in))
        break

#

经过一些 COMMENTS/ANSWERS 原始问题的编辑

在这个问题里面，又来了一个新问题。我正在为一个平台构建它。我的解决方案是正确的。在 Blender 的评论之后。我这样做了（这是我最初的解决方案）：

def lcm_fast(a,b):
    a = ((a*b)/(euclidean_gcd(a,b)))
    return a

问题是我在平台的测试用例上收到此消息失败：

Failed case #1/42: Cannot check answer. Perhaps output format is wrong. 

Input: 18 35 Your output: 630.0 Correct output: 630 (Time used: 0.01/5.00, memory used: 9613312/536870912.)

这很有趣。如果我避免使用 int() 进行近似，则该代码适用于大数。但是，如果没有从 float 到 int 的转换，我无法提供所需格式的答案。

Answer 1

您要使用 int() 将除法结果转换回整数，因为 "regular" 整数除法会产生浮点数。 CPython 的浮点数具有固定的精度，因此您的来回转换将导致足够大的数字丢失信息。

避免丢失精度并使用 // 执行底除法，其中 returns 一个整数：

def lcm_fast(a,b):
    return (a * b) // euclidean_gcd(a,b)

Answer 2

在python3中，标准除法（/）运算会自动提升为浮点数，而整数除法（//）总是return一个int.

因此，python 可以处理任意大的 ints，在某些时候，您的数据被视为 float 而不是 int，使其出现浮点精度错误。

（我在写这篇文章的时候看到其他人也输入了类似的答案，我觉得有义务在因为复制别人的答案而被殴打致死之前记下这一点。）

用 Python 编写的求最小公倍数算法中的奇怪错误

Strange error in an algorithm written in Python to find the Least Common Multiple

stress-testing

python-3.x

greatest-common-divisor