Mô phỏng trên có thể chuyển trực tiếp sang thành một chương trình trong đó sử dụng một thủ tục để tính giá trị của đa thức bậc N-1 tại các căn bậc N của đơn vị. Tuy nhiên, các phép toán này thực hiện trên số phức mà trong Pascal lại không có xây dựng kiểu số phức. Do đó, ta cần có một thủ tục để xác định kiểu số phức cũng như các phép toán trên các số này. Với giả định là kiểu số phức ta đã có, ta có chương trình tính giá trị sau: 

eval(p,outN, 0);

eval(q, outN, 0);

for i:= 0 to outNdo r[i]:= p[i]*q[i];

eval(r,outN, 0);

for i:=1 to N do

begin t:= r[i]; r[i]:= r[outN+1]; r[outN+1-i]:= t; end;

for i:=0 to outN do r[i]:=r[i]/(outN+1);

Trong chương trình này, ta giả sử biến toàn cục outN là 2N-1 và q, p, r là các mảng số phức đánh từ 0 tới 2N-1. Hai đa thức được nhân q.p có cấp N-1 và các hệ số thêm vào để được mảng 2N-1 phần tử là các số không. Thủ tục eval thay các hệ số đã cho như là biến thứ nhất của đa thức bởi các giá trị cảu đa thức tính tại các căn của đơn vị. Biến thứ hai xác định bậc của đa thức bà biến thứ ba sẽ mô tả dưới đây. Chương trình trên tính tích của p.q và để kết quả ở mảng r.

Tuy nhiên, chương trình đệ quy có các mảng có thể gây khó khăn khi cài đặt. Ngoài ra, còn một bài toán thông thường là quản lý vùng chứa bằng cách dùng lại nó một cách thông minh. Điều ta cần ở đây là có một thủ tục đệ quy đưa vào một mảng N+1 hệ số và cho ra N+1 giá trị trong cùng một mảng. Tuy nhiên, quá trình đệ quy lại bao gồm việc xử lý hai mảng rời nhau: các hệ số lẻ và chẵn. Sự xáo trộn lý tưởng là cái mà ta cần. Ta có thể đưa các hệ số lẻ vào trong một mảng con (nửa đầu) và các hệ số chẵn vào một mảng con (nửa sau) bằng cách thực hiện sự “không xáo trộn lý tưởng” của dữ liệu nhập.

Dĩ nhiên các giá trị căn số phức cũng cần cài đặt. Ta có:

wⁱ_N = cos(2∏j/(N+1) + isin(2∏j/(N+1))

Sử dụng các hàm lượng giác quy ước ta có thể tính dễ dàng giá trị w_Nj. Trong chương trình dưới đây, mảng w được giả định là chứa các căn bậc (outN+1) của đơn vị.

Ta có chương trình sau:

procedure eval(var p:poly; N, k: integer);

var i, j: integer;

begin

if N=1

then begin t:=p[k]; p1:= p[k+1]; p[k]:= t+p1; p[k+1]:= t-p1;

end

else begin

for i:= 0 to N div 2 do

begin j:= k+2*i; t[i]:= p[j]; t[t+1+N div 2]: = p[j] +1;

end;

fori:= 0 to N do p[k+i]:= t[i];

eval(p,N div 2, k);

eval(p, N div 2, k +1 +N div 2);

j:= (outN +1) div (N+1);

for i:= 0 to N div 2 do

begin t:= w[i*j]*p[k+(N div 2)+ 1 +i];

t[i]:= p[k+i]+t; t[i+ N div 2) +1]:= p[k+i]*t

end;

for i:=0 to N do p[k+i]:= t[i]

end;

end;

Chương trình này chuyển đa thức bậc N vào mảng con p[k…k+N] bằng cách dùng phương pháp đệ quy. (Để đơn giản, mã này giả sử rằng N+1 là một luỹ thừa của 2, mặc dầu điều này bỏ đi dễ dàng). Nếu N=1, ta dễ dàng tính giá trị tại 1 và -1. Với N≠ 1 thủ tục này đầu tiên sẽ xáo trộn, rồi gọi đệ quy chính nó để chuyển sang bài toán cho N/2, sau đó kết hợp các kết quả tính toán như đã mô tả trên. Để nhận được các căn vị cần thiết, chương trình chọn từ mảng tại một khoảng các định bởi biến i. Ví dụ, nếu outN=15, các căn bậc 4 của đơ nvị tìm thấy trong w[0], w[4], w[8], w[12]. Điều này làm giảm bớt số tính toán các căn của đơ nvị sử dụng.

*** Hai đa thức cấp N có thể được nhân 2NlgN + 0(N) phép nhân phức.

Sự áp dụng phương pháp ở thuật toán trên rộng hơn nhiều so với phép toán nhân hai đa thức mà chúng ta trình bày ở trên; và thuật toán này đã được sử dụng mạnh và khảo sát trong nhiều lĩnh vực khác nhau. Tuy nhiên, các nguyên tắc chính trong các áp dụng cũng tương tự như trong việc nhân đa thức được xem xét ở đây. Phương pháp này là một ví dụ cổ điển về phương pháp “chia-để - trị”.

School@net (Theo THNT)