câu hỏi về phép nhân karatsuba

Question

Tôi muốn thực hiện Karatsuba's 2-split multiplication bằng Python. Tuy nhiên, viết số dưới dạng

A=c*x+d 

trong đó x là một sức mạnh của các cơ sở (giả sử x = b^m) gần sqrt (A).

Làm cách nào để tìm x, nếu tôi thậm chí không thể sử dụng phép chia và nhân? Tôi có nên đếm số chữ số và dịch chuyển A sang bên trái bằng một nửa số chữ số không?

Cảm ơn.

Answer 1

Hầu như. Bạn không thay đổi A bằng một nửa số chữ số; bạn thay đổi 1. Tất nhiên, điều này chỉ hiệu quả nếu cơ sở là một sức mạnh của 2, vì "chuyển dịch" trong cơ sở 10 (ví dụ) phải được thực hiện với phép nhân. (Chỉnh sửa: tốt, ok, bạn có thể nhân với ca và bổ sung. Nhưng nó đơn giản hơn rất nhiều với sức mạnh của 2.)

Nếu bạn đang sử dụng Python 3.1 trở lên, việc đếm các bit rất dễ dàng, vì 3.1 đã giới thiệu phương pháp int.bit_length(). Đối với các phiên bản Python khác, bạn có thể đếm số bit bằng cách sao chép A và dịch chuyển sang phải cho đến khi 0. Điều này có thể được thực hiện trong thời gian O (log N) (N = # chữ số) với một loại phương pháp tìm kiếm nhị phân nhiêu bit, nếu đó là 0 thì đó là quá nhiều, vv

Answer 2

bạn đã chấp nhận một câu trả lời kể từ khi tôi bắt đầu viết những dòng này, nhưng:

gì Tom nói: bằng Python 3.x bạn có thể nhận được n = int .bit_length() trực tiếp. Trong Python 2.x bạn nhận được n trong thời gian O (log2 (A)) bằng cách tìm kiếm nhị phân, như dưới đây.

Đây là (2.x) mã tính cả hai. Để số mũ cơ số 2 của x là n, tức là x = 2 ** n.

Đầu tiên chúng tôi nhận được n bằng tìm kiếm nhị phân bằng cách dịch chuyển. (Thực sự chúng tôi chỉ cần n/2, vì vậy đó là một lần lặp lại không cần thiết cuối cùng). Sau đó, khi chúng ta biết n, nhận được x, c, d là dễ dàng (vẫn không có bộ phận sử dụng)

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

Câu hỏi của bạn đã được trả lời trong bài viết mà bạn gọi: "bước cơ bản Karatsuba của việc cho bất kỳ cơ sở B và bất kỳ m, nhưng thuật toán đệ quy hiệu quả nhất khi m bằng n/2, được làm tròn lên "... n là số chữ số và 0 < = value_of_digit < B.

Một số góc nhìn có thể giúp :

Bạn được phép (và bắt buộc!) Để sử dụng hoạt động tiểu học như number_of_digits // 2 và divmod(digit_x * digit_x, B) ... trong số học, trong đó B là 10, bạn được yêu cầu (ví dụ) để biết rằng divmod(9 * 8, 10) sản xuất (7, 2).

Khi thực hiện số học số lớn trên máy tính, thông thường để B trở thành công suất lớn nhất của 2 sẽ hỗ trợ thao tác nhân sơ cấp thuận tiện. Ví dụ trong việc triển khai CPython trên máy 32 bit, B được chọn là 2 ** 15 (tức là 32768), bởi vì sau đó product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF; hoạt động mà không tràn và không quan tâm đến bit dấu.

Tôi không chắc những gì bạn đang cố gắng đạt được với triển khai bằng Python sử dụng B == 2, với số được biểu diễn bằng Python ints, thực hiện trong C đã sử dụng thuật toán Karatsuba để nhân số đủ lớn để làm cho nó đáng giá. Nó không thể là tốc độ.

Là bài tập học tập, bạn có thể muốn thử đại diện một số dưới dạng danh sách các chữ số, với cơ số B là tham số đầu vào.