Seltsamer Fehler in einem Algorithmus in Python geschrieben, um den kleinsten gemeinsamen Multiple zu finden

Question

Für pädagogische Zwecke versuche ich einen effizienten Algorithmus zu erstellen, um das Least Common Multiple zu finden. Ich habe dafür bereits eine quadratische und langsame Implementierung. Ich versuche, ein neues zu bauen. Meine neue Implementierung verwendet eine mathematische Eigenschaft, die den größten gemeinsamen Teiler (GCD) und den kleinsten gemeinsamen Teiler (LCM) umfasst.

Grundsätzlich gilt: Für jede zwei positive ganze Zahlen a und b,

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

Ich bin mit Python 3 dafür.

ich eine sehr effiziente Implementierung für GCD (es verwendet eine andere mathematische Eigenschaft, aber es ist sinnlos, darüber zu sprechen):

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

Meine Implementierung für LCM ist: Jedoch

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

, wenn ich rufe:

lcm_fast(1023473145,226553150) 

ich als Ausgabe erhalten:

46374212988031352 

Die richtige Antwort eine enge Zahl sein würde:

46374212988031350 

Ich bin ein Anfänger (zweites Jahr auf der Applied Math-Dur), warum ist das passiert?

Ich bin nicht sicher, ob ich das Konzept des Integer-Überlaufs erfassen könnte, aber nach meinem Verständnis oben ein wenig Forschung, die ich tat, gibt es keinen Integer-Überlauf in Python.

Ich habe Stresstests gemacht und versucht, diesen Fehler in einem einfacheren Fall zu finden. Das Problem scheint jedoch nur mit wirklich großen Zahlen zu passieren. Bellow Sie meinen Stress für das Testen überprüfen:

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 

#

EDITED NACH einige Kommentare/ANTWORTEN AUF DAS ORIGINAL PROBLEM

Innerhalb dieses Problem kommt ein neues Problem. Ich baue das für eine Plattform. Meine Lösung ist richtig. Nach dem Kommentar von Blender. Das habe ich (das war meine ursprüngliche Lösung):

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

Das Problem ist, dass ich diese Meldung auf der Plattform von Testfällen versagt:

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.) 

Das ist lustig. Wenn ich die Annäherung mit int() vermeide, ist der Code für große Zahlen richtig. Aber ohne die Konvertierung von float zu int kann ich die Antwort auf das gewünschte Format nicht liefern.

Answer 1

Sie konvertieren das Ergebnis Ihrer Division zurück in eine Ganzzahl mit int(), weil "normale" Ganzzahldivision zu einem Float führt. Die Floats von CPython haben eine feste Genauigkeit, so dass Ihre Konvertierung hin und her zu verlorenen Informationen für ausreichend große Zahlen führt.

Vermeiden Präzision zu verlieren und Boden Teilung durchführen mit //, die eine ganze Zahl zurückgibt:

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

Answer 2

In Python 3, Standard-Division (/) Operationen automatisch zu schweben, während Integer-Division (//) fördern wird immer eine int zurückgeben.

So kann Python beliebig große int s behandeln, an einem bestimmten Punkt werden Ihre Daten als Float und nicht als Int behandelt, wodurch sie einem Gleitkomma-Präzisionsfehler unterzogen wird.

(ich sehe jemand anderes auch eine ähnliche Antwort getippt, während ich dies oben schreibe und fühlt sich verpflichtet, dies zur Kenntnis zu machen, bevor für das Kopieren von jemandem anderer Antwort auf dem Tod heftig geschlagen zu werden.)