pregunta sobre la multiplicación de karatsuba

Question

Quiero implementar Karatsuba's 2-split multiplication en Python. Sin embargo, los números de escritura en forma

A=c*x+d 

donde x es una potencia de la base (sea x = b^m) cerca de sqrt (A).

¿Cómo se supone que encuentre x, si ni siquiera puedo usar la división y la multiplicación? ¿Debería contar el número de dígitos y desplazar A a la izquierda a la mitad del número de dígitos?

Gracias.

Answer 1

Casi. No cambia A por la mitad del número de dígitos; cambias 1. Por supuesto, esto solo es eficiente si la base es una potencia de 2, ya que "cambiar" en la base 10 (por ejemplo) tiene que hacerse con multiplicaciones. (Edit:. Bueno, está bien, se puede multiplicar con los cambios y adiciones Pero es cada vez mucho más sencillo con una potencia de 2.)

Si está utilizando Python 3.1 o superior, contando los bits es fácil, porque 3.1 introdujo el método int.bit_length(). Para otras versiones de Python, puede contar los bits copiando A y moviéndolo hacia la derecha hasta que sea 0. Esto se puede hacer en tiempo O (log N) (N = # de dígitos) con una especie de método de búsqueda binario - cambiar por muchos bits, si es 0 entonces que era demasiado, etc.

Answer 2

ya has aceptado una respuesta desde que empecé a escribir esto, pero:

lo que Tom dijo: en Python 3.x puede obtener n = int .bit_length() directamente. En Python 2.x obtiene n en O (log2 (A)) tiempo por búsqueda binaria, como a continuación.

Aquí está el código (2.x) que calcula ambos. Deje que el exponente base-2 de x sea n, es decir, x = 2 ** n.

Primero obtenemos n mediante la búsqueda binaria por desplazamiento. (Realmente solo necesitábamos n/2, así que esa es una última iteración innecesaria). Luego, cuando sabemos n, consiguiendo x, c, d es fácil (todavía sin usar división)

def karatsuba_form(A,n=32): 
    """Binary-search for Karatsuba form using binary shifts""" 
    # First search for n ~ log2(A) 
    step = n >> 1 
    while step>0: 
     c = A >> n 
     print 'n=%2d step=%2d -> c=%d' % (n,step,c) 
     if c: 
      n += step 
     else: 
      n -= step 
     # More concisely, could say: n = (n+step) if c else (n-step) 
     step >>= 1 
    # Then take x = 2^(n/2) ˜ sqrt(A) 
    ndiv2 = n/2 
    # Find Karatsuba form 
    c = (A >> ndiv2) 
    x = (1 << ndiv2) 
    d = A - (c << ndiv2) 
    return (x,c,d) 

Answer 3

Su pregunta ya está contestada en el artículo al que se hace referencia: "paso básico de Karatsuba funciona para cualquier base B y cualquier m, pero el algoritmo recursivo es más eficiente cuando m es igual a n/2, redondeado" ... n siendo el número de dígitos, y 0 < = value_of_digit < B.

Algunos perspectiva que podría ayudar :

Se le permite (y se requiere) utilizar elemental operaciones como number_of_digits // 2 y divmod(digit_x * digit_x, B) ... en aritmética escolar, donde B es 10, se le requiere (por ejemplo) saber que divmod(9 * 8, 10) produce (7, 2).

Al implementar la aritmética de números grandes en una computadora, es habitual hacer B la potencia más grande de 2 que admitirá la operación de multiplicación elemental convenientemente. Por ejemplo, en la implementación de CPython en una máquina de 32 bits, B se elige para que sea 2 ** 15 (es decir, 32768), porque entonces product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; funciona sin desbordamiento y sin preocuparse por un bit de signo.

No estoy seguro de lo que intenta lograr con una implementación en Python que usa B == 2, con números representados por Python, cuya implementación en C ya usa el algoritmo Karatsuba para multiplicar números que son lo suficientemente grandes para que valga la pena No puede ser velocidad.

Como ejercicio de aprendizaje, puede intentar representar un número como una lista de dígitos, siendo la base B un parámetro de entrada.