Algorytm Karacuby do mnożenia wielomianów

Algorytm Karacuby do mnożenia wielomianów
nowy121105
N1
nowy121105
N1
  • Rejestracja:ponad 19 lat
  • Ostatnio:5 miesięcy
0

Na kanale Przemysława Koprowskiego widziałem następujący pseudokod algorytmu Karacuby

Kopiuj
Algorytm Karacuby

Wejście : wielomiany
      f = f[0] + f[1]x+f[2]x^2+...+f[m]x^m
      g = g[0] + g[1]x+g[2]x^2+...+g[n]x^n
Wyjście h = f*g = h[0]+h[1]x+...+h[k]x^k

1. Jeżeli f = 0 lub g = 0, to    
   zwróć 0 i zakończ
2. Jeżeli oba wielomiany są stałe
   to zwróć f[0]*g[0] i zakończ
3. Przyjmij d := Ceil(max(deg f,deg g)/2)
4. Rozdziel oba wielomiany na części "górną" i "dolną"
   fl := f[0]+f[1]x+...+f[d-1]x^{d-1},  fu := f[d] + f[d+1]x+...+f[m]x^{m-d}
   gl := g[0]+g[1]x+...+g[d-1]x^{d-1},  gu := g[d] + g[d+1]x+...+g[n]x^{n-d}
5. Wywołaj algorytm rekurencyjnie i policz
   fl*gl , fu*gu , (fl + fu)(gl + gu)
6. Scal otrzymane wyniki
   h = fl*gl + ((fl + fu)(gl + gu) - fl*gl - fu*gu)x^d + fu*gu x^{2d}

Napisałem moduł do obsługi wielomianów zdefiniowanych następująco

Kopiuj
type TPolynomial = record
                     deg:integer;
                     coeff:array of Double;    
                   end;

Mam w nim mnożenie ale takie standardowe , te znane ze szkoły

Źródło tego pseudokodu to


gdzieś w okolicach 32:23

Problem z tym pseudokodem jest taki że wg mnie niepoprawnie dzieli te wielomiany na części dolną i górną
Gdybyśmy chcieli na podstawie tego pseudokodu napisać funkcję realizującą mnożenie wielomianów to mogłaby się zdarzyć sytuacja że
wyszlibyśmy indeksem poza tablicę przechowującą współczynniki

Jak ten pseudokod poprawić ?

...

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
lion137
lion137
lion137
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:3 minuty
  • Postów:4884
0

Możesz podać kontrprzykład dla punktu czwartego pseudokodu?

edytowany 1x, ostatnio: lion137
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
nowy121105
N1
nowy121105
N1
  • Rejestracja:ponad 19 lat
  • Ostatnio:5 miesięcy
0

Dla wielomianów

Kopiuj
9x^4 + 7x^3 + 4x^2 + 8x +  9
8x^7+ 4x^6+ 2x^5 + x^4 + 6x^3 + 5x^2+ 9x+ 4

źle podzieli bo w pewnym momencie d będzie większe od stopnia któregoś z wielomianów f lub g.

edytowany 1x, ostatnio: flowCRANE
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
lion137
lion137
lion137
lion137
  • Rejestracja:około 8 lat
  • Ostatnio:3 minuty
  • Postów:4884
0

To chyba powinieneś uzupełniać zerami, bo i tak operujesz na tablicach.

Zobacz pozostały 1 komentarz
lion137
Wrzuć, chociaż od Pascala tutaj nie jestem ekspertem
GO
Kompilujesz z parametrem -g co daje ci symbole debuggera w pliku wykonywalnym, teraz jak odpalisz debugger gdb, to on wie, który kod ma jakąś linijkę kodu, i możesz zanalizować tu i tu, w gdb wpiszuesz tui enable, i widzisdz kod źródłowy i gdzie jesteś. Ale co chcesz z debuggera wyciągnąć, bo jak algorytmu nie znasz w ogóle to debuggowanie ci nic nie da, bo on będzie taki sam ten algorytm jak wcześniej, ale gorzej zapisany czyli w assemblerze zwykle.
N1
lion nie jesteś ekpertem ale znasz go choć trochę Myślę że jeśli znasz podstawy angielskiego to będziesz w stanie przeczytać kod
N1
"bo jak algorytmu nie znasz w ogóle" Samą ideę tego algorytmu znam problem w tym że pseudokod jest błędnie zapisany Po co gdy u innego gościa znalazłem poprawnie zapisany pseudokod metody Bairstowa to nie miałem problemu z jego zapisaniem
GO
Akurat tego algorytmu nie znam, a jak znam to mam swoją implementację w głowie więc jest łatwiej, tu jak nie było crasha aplikacji to debugger dużo nie pomoże, ale jak znasz dobrze algorytm to zrób sobie na początku programu breakpoint i idź po jednej funkcji i sprawdzaj czy wyniki się zgadzają z operacjami jakie powinny być
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
nowy121105
N1
nowy121105
N1
  • Rejestracja:ponad 19 lat
  • Ostatnio:5 miesięcy
0

Tak jak zasugerowałeś próbowałem uzupełniać zerami ale nic z tego nie wyszło

Moduł do obsługi wielomianów

Kopiuj

unit Polynomial;
interface
uses math;

const ZERO = 1e-10;

type TPolynomial = record
                     deg:integer;
                     coeff:array of Double
                   end;

function MakePolynomial(n:integer):TPolynomial;
function Equals(a,b:TPolynomial):boolean;
function AddPolynomials(a,b:TPolynomial):TPolynomial;
function SubtractPolynomials(a,b:TPolynomial):TPolynomial;
function MultiplyPolynomials(a,b:TPolynomial):TPolynomial;
function DividePolynomials(a,b:TPolynomial;var r:TPolynomial):TPolynomial;
function Horner(p:TPolynomial;x:Double):Double;
procedure WritePolynomial(p:TPolynomial;c:char);

implementation



function MakePolynomial(n:integer):TPolynomial;
var p:TPolynomial;
begin
  p.deg := n;
  SetLength(p.coeff,n+1);
  MakePolynomial := p
end;

procedure FindDeg(var p:TPolynomial);
var i:integer;
begin
  for i := p.deg downto 0 do
    if abs(p.coeff[i]) > ZERO then
    begin
      p.deg := i;
      Exit;
    end;
    p.deg := 0
end;

function AddPolynomials(a,b:TPolynomial):TPolynomial;
var newDeg,range,i:integer;
    n:TPolynomial;
begin
  if a.deg >  b.deg then
     newDeg := a.deg
  else
     newDeg := b.deg;
  range := newDeg - abs(a.deg - b.deg);
  n := MakePolynomial(newDeg);
  for i := range downto 0 do
     n.coeff[i] := a.coeff[i] + b.coeff[i];
  if a.deg > b.deg then
     for i := newDeg downto range+1 do
        n.coeff[i] := a.coeff[i]
  else
     for i := newDeg downto range+1 do
        n.coeff[i] := b.coeff[i];
  findDeg(n);
  AddPolynomials := n
end;

function SubtractPolynomials(a,b:TPolynomial):TPolynomial;
var newDeg,range,i:integer;
    n:TPolynomial;
begin
  if a.deg >  b.deg then
     newDeg := a.deg
  else
     newDeg := b.deg;
  range := newDeg - abs(a.deg - b.deg);
  n := MakePolynomial(newDeg);
  for i := range downto 0 do
     n.coeff[i] := a.coeff[i] - b.coeff[i];
  if a.deg > b.deg then
     for i := newDeg downto range+1 do
        n.coeff[i] := a.coeff[i]
  else
     for i := newDeg downto range+1 do
        n.coeff[i] := -b.coeff[i];
  findDeg(n);
  SubtractPolynomials := n
end;

function MultiplyPolynomials(a,b:TPolynomial):TPolynomial;
var i,j:integer;
    n:TPolynomial;
begin
   n := MakePolynomial(a.deg + b.deg);
   for i := 0 to n.deg do
     n.coeff[i] := 0;
   for i := 0 to a.deg do
      for j := 0 to b.deg do
         n.coeff[i + j] := n.coeff[i + j] + a.coeff[i] * b.coeff[j];
   MultiplyPolynomials := n
end;

function DividePolynomials(a,b:TPolynomial;var r:TPolynomial):TPolynomial;
var q,temp:TPolynomial;
    i,j,qdeg:integer;
begin
  if a.deg < b.deg then
     qdeg := 0
  else
     qdeg := a.deg;
  q := MakePolynomial(qdeg);
  if q.deg = 0 then
  begin
    q.coeff[0] := 0;
    r.deg := a.deg;
    for i :=r.deg downto 0 do
       r.coeff[i] := a.coeff[i];
       DividePolynomials := q;
       Exit
  end;
  temp := MakePolynomial(a.deg);
  for i := 0 to a.deg do
  begin
    temp.coeff[i] := a.coeff[i];
    q.coeff[i] := 0
  end;
  for i := a.deg - b.deg downto 0 do
  begin
    q.coeff[i] := temp.coeff[b.deg + i] /b.coeff[b.deg];
    for j := b.deg + i - 1 downto i do
       temp.coeff[j] := temp.coeff[j] - q.coeff[i] * b.coeff[j - i]
  end;
  for i := 0 to b.deg - 1 do
      r.coeff[i] := temp.coeff[i];
  if r.deg < a.deg then
     for i := b.deg to r.deg do
         r.coeff[i] := 0
     else
        for i := b.deg to a.deg do
           r.coeff[i] := 0;
     findDeg(r);
     findDeg(q);
     DividePolynomials := q
end;

function Equals(a,b:TPolynomial):boolean;
var bool : boolean;
    i : integer;
begin
  bool := a.deg = b.deg;
  i := a.deg;
  while bool and (i >= 0) do
  begin
    bool := bool and (a.coeff[i] = b.coeff[i]);
    Dec(i)
  end;
  Equals := bool
end;

procedure  WritePolynomial(p:TPolynomial;c:char);
var i:integer;
begin
  for i := p.deg downto 0 do
      if p.coeff[i] < 0 then
         write(p.coeff[i]:1:12,'*',c,'^',i)
      else
         write('+',p.coeff[i]:1:12,'*',c,'^',i);
  writeln
end;

function Horner(p:TPolynomial;x:Double):Double;
var v:double;
    i:integer;
begin
  v := p.coeff[p.deg];
  for i := p.deg - 1 downto 0 do
     v := v * x + p.coeff[i];
  Horner := v
end;

begin

end.

Kod programu do testowania funkcji realizującej algorytm Karacuby

Kopiuj



program untitled;

uses crt,math,polynomial;

function Karatsuba(f,g:TPolynomial):TPolynomial;
var temp1,temp2:TPolynomial;
    h,h1,h2,h3:TPolynomial;
    k,d:integer;
begin
  if ((f.deg = 0)and(f.coeff[0] = 0)) or ((g.deg = 0)and(g.coeff[0] = 0)) then
  begin
    h := makePolynomial(0);
    h.coeff[0] := 0;
    Karatsuba := h;
    Exit
  end;
  if ((f.deg = 0) and (g.deg = 0)) then
  begin
    h := makePolynomial(0);
    h.coeff[0] := f.coeff[0] * g.coeff[0];
    Karatsuba := h;
    Exit
  end;
  begin
    d := max(f.deg,g.deg);
    d := Ceil(0.5 * d);
    temp1 := makePolynomial(d-1);
    for k := 0 to min(d - 1,f.deg) do
        temp1.coeff[k] := f.coeff[k];
    for k := min(d-1,f.deg) + 1 to d - 1 do
        temp1.coeff[k] := 0;
    temp2 := makePolynomial(d-1);
    for k := 0 to min(d - 1,g.deg) do
        temp2.coeff[k] := g.coeff[k];
    for k := min(d - 1,g.deg) + 1 to d - 1 do
        temp2.coeff[k] := 0;
    h1 := Karatsuba(temp1,temp2);
    temp1 := makePolynomial(ord((f.deg - d)>=0)*(f.deg - d));
    for k := 0 to temp1.deg do
       temp1.coeff[k] := f.coeff[k + d];
    temp2 := makePolynomial(ord((g.deg - d)>=0)*(g.deg - d));
    for k := 0 to temp2.deg do
       temp2.coeff[k] := g.coeff[k+d];
    h2 := Karatsuba(temp1,temp2);
    temp1 := makePolynomial(d-1);
    temp2 := makePolynomial(ord((g.deg - d)>=0)*(g.deg - d));
    for k := 0 to min(d - 1,g.deg) do
       temp1.coeff[k] := g.coeff[k];
    for k := min(d - 1,g.deg) + 1 to d-1 do
        temp1.coeff[k] := 0;
    for k := 0 to temp2.deg do
       temp2.coeff[k] := g.coeff[k+d];
    h3 := AddPolynomials(temp1,temp2);
    for k := 0 to min(d - 1,f.deg) do
       temp1.coeff[k] := f.coeff[k];
    for k := min(d - 1,f.deg) + 1 to d - 1 do
       temp1.coeff[k] := 0;
    temp2 := makePolynomial(ord((f.deg - d)>=0)*(f.deg - d));
    for k := 0 to temp2.deg do
       temp2.coeff[k] := f.coeff[k+d];
    temp1 := AddPolynomials(temp1,temp2);
    h3 := Karatsuba(temp1,h3);
    temp1 := SubtractPolynomials(h3,h1);
    temp1 := SubtractPolynomials(temp1,h2);
    temp2 := makePolynomial(temp1.deg+d);
    for k := 0 to temp1.deg do
       temp2.coeff[k + d] := temp1.coeff[k];
    for k := 0 to d - 1 do
       temp2.coeff[k] := 0;
    h := AddPolynomials(h1,temp2);
    temp2 := makePolynomial(h2.deg + 2*d);
    for k := 0 to h2.deg do
        temp2.coeff[k + 2*d] := h2.coeff[k];
    for k := 0 to 2*d - 1 do
        temp2.coeff[k] := 0;
    h := AddPolynomials(h,temp2);
    Karatsuba := h;
  end;
end;

var f:text;
	k,n,m:integer;
	a,b,c:TPolynomial;

BEGIN
	
Assign(f,'input.txt');
Reset(f);
ReadLn(f,n);
a := makePolynomial(n);
k := n;
while not Eoln(f) do 
begin
Read(f,a.coeff[k]);
k:=k-1;
end;
ReadLn(f,m);
b := makePolynomial(m);
k := m;
while not Eoln(f) do 
begin
Read(f,b.coeff[k]);
k:=k-1;
end;
WriteLn('Polynomial a');
WriteLn(a.deg);
writePolynomial(a,'x');
WriteLn('Polynomial b');
WriteLn(b.deg);
writePolynomial(b,'x');
c := Karatsuba(a,b);
WriteLn('Polynomial c');
WriteLn(c.deg);
writePolynomial(c,'x');
Close(f);	
END.

Podobno błąd zakresu jest gdzieś w linii 42

Zobacz pozostałe 14 komentarzy
GO
Jak o big num ci chodzi to co innego, to akurat znam, ale czemu na wielomianach chcesz to robić,można dobrze na prawdopodobieństwie jest funkcja, która określa jakie będą przyszłe liczby czyli taki gasussian process, ale to się nadaje do specyficznych przypadków., nie znam tego algorytmu jutro spojrzę na to po pracy, może mi si się przyda do czegoś. Ogólnie lubię matme.
N1
W sumie to tylko zabawa gdybym miał jakiś własny gmp napisać to musiałbym się poduczyć obiektowego Pascala bo dla strukturalnego to dll z gmp widziałem tylko wygląda on jakby był przeniesiony z C tylko mało w sieci do tego materiałów Oryginalnie algorytm Karacuby przeznaczny był dla mnożenia liczb ale da się go przenieść na wielomiany Jak miałeś do czynienia z jakimś big numem to obok FFT algorytm Karacuby jest jednym z algorytmów mnożenia FFT jest szybszy ale wymaga zabawy z zespolonymi choć obecnie nie jest to aż taki wielki problem
GO
FFT czyli furier transform fajnie brzmi, lubię to :>
GO
Nie no FFT to kompletny bull shit z twojej strony
N1
Ja go tutaj nie używam ale wiem że w big numach lubią z niego korzystać bo jest szybki Jeżeli chcesz poczytać o algorytmie Karacuby w oryginale to wpisz Алгоритм Карацубы Gościu był Rosjaninem i żył za czasów Sajuza Ja niestety za późno się urodziłem aby znać ten piękny język Jego córka Kasia Karacuba ma stronę internetową więc można by spróbować zasięgnąć języka u źródła Problem w tym że prawdopodobieństwo że odpowie jest bliskie zeru , dodatkowo trzeba znać albo rosyjski albo angielski a ja rosyjskiego nie znam w ogóle a angielski dość kiepsko
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
flowCRANE
flowCRANE
flowCRANE
flowCRANE
Moderator Delphi/Pascal
  • Rejestracja:ponad 13 lat
  • Ostatnio:2 minuty
  • Lokalizacja:Tuchów
  • Postów:12164
2

@nowy121105: postaw break point w linii 42 i sprawdź jakie wartości mają zmienne lokalne. Tylko w ten sposób dowiesz się dlaczego dostajesz range check error.

Pracuję nad własną, arcade'ową, docelowo komercyjną grą z gatunku action/adventure w stylu retro (pixel art), programując silnik i powłokę gry od zupełnych podstaw, przy użyciu Free Pascala i SDL3. Więcej informacji znajdziesz na moim mikroblogu.
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
nowy121105
N1
nowy121105
N1
  • Rejestracja:ponad 19 lat
  • Ostatnio:5 miesięcy
0
Kopiuj
program untitled;

uses crt,math,polynomial;

function Karatsuba(f,g:TPolynomial):TPolynomial;
var temp1,temp2:TPolynomial;
    h,h1,h2,h3:TPolynomial;
    k,m,n,d:integer;
begin
 //Base case f = 0 or g = 0
  if ((f.deg = 0)and(f.coeff[0] = 0)) or ((g.deg = 0)and(g.coeff[0] = 0)) then
  begin
    h := makePolynomial(0);
    h.coeff[0] := 0;
    Karatsuba := h;
    Exit
  end;
  //Base case both polynomials are constant
  if ((f.deg = 0) and (g.deg = 0)) then
  begin
    h := makePolynomial(0);
    h.coeff[0] := f.coeff[0] * g.coeff[0];
    Karatsuba := h;
    Exit
  end;
  begin
  //Checking which polynomial has maximum degree
    d := max(f.deg,g.deg); 
    //Calculating ceiling of half of max degree  
    d := (d + 1) div 2;
    //Creating temporary polynomial which stores lower part of polynomial f
    m := 1 + min(d - 1,f.deg);
    temp1 := makePolynomial(m-1);
    for k := 0 to m - 1 do
      temp1.coeff[k] := f.coeff[k];
     //Creating temporary polynomial which stores lower part of polynomial g
     n := 1 + min(d - 1,g.deg);
    temp2 := makePolynomial(n-1);
    for k := 0 to n - 1 do
       temp2.coeff[k] := g.coeff[k];
    //Recursive call of function Karatsuba to calculate product flow * glow
    h1 := Karatsuba(temp1,temp2);
    //Creating temporary polynomial which stores upper part of polynomial f
    temp1 := makePolynomial(ord(f.deg - m >= 0)*(f.deg - m));
    temp1.coeff[0] := 0;
    for k := 0 to f.deg - m do
       temp1.coeff[k] := f.coeff[k + m];
    //Creating temporary polynomial which stores upper part of polynomial g
    temp2 := makePolynomial(ord(g.deg - n >= 0)*(g.deg - n));
    temp2.coeff[0] := 0;
    for k := 0 to g.deg - n do
       temp2.coeff[k] := g.coeff[k+n];
    //Recursive call of function Karatsuba to calculate product fup * gup  
    h2 := Karatsuba(temp1,temp2);
    //Creating temporary polynomial to store lower part of polynomial g
    temp1 := makePolynomial(n-1);
    //Creating temporary polynomial to store upper part of polynomial g
    temp2 := makePolynomial(ord(g.deg - n >= 0)*(g.deg - n));
    for k := 0 to n - 1 do
       temp1.coeff[k] := g.coeff[k];
    temp2.coeff[0] := 0;
    for k := 0 to g.deg - n do
       temp2.coeff[k] := g.coeff[k+n];
    //Creating polynomial glow + gup
    h3 := AddPolynomials(temp1,temp2);
    //Set coefficients of temporary polynomial to coefficients of lower part of polynomial f
    for k := 0 to m - 1 do
       temp1.coeff[k] := f.coeff[k];
    //Creating temporary polynomial which stores upper part of polynomial f  
    temp2 := makePolynomial(ord(f.deg - m >= 0)*(f.deg - m));
    temp2.coeff[0] := 0;
    for k := 0 to f.deg - m do
       temp2.coeff[k] := f.coeff[k+m];
    //Creating polynomial flow + fup  
    temp1 := AddPolynomials(temp1,temp2);
    //Recursive call of function Karatsuba to calculate product (flow + fup)*(glow + gup)
    h3 := Karatsuba(temp1,h3);
    //Merging results , calculation middle terms
    temp1 := SubtractPolynomials(h3,h1);
    temp1 := SubtractPolynomials(temp1,h2);
    temp2 := makePolynomial(temp1.deg+d);
    for k := 0 to temp1.deg do
       temp2.coeff[k + d] := temp1.coeff[k];
    for k := 0 to d - 1 do
       temp2.coeff[k] := 0;
    //Adding lower part and middle part
    h := AddPolynomials(h1,temp2);
    //Creating upper part
    temp2 := makePolynomial(h2.deg + 2*d);
    for k := 0 to h2.deg do
        temp2.coeff[k + 2*d] := h2.coeff[k];
    for k := 0 to 2*d - 1 do
        temp2.coeff[k] := 0;
    //Adding upper part to current result
    h := AddPolynomials(h,temp2);
    Karatsuba := h;
  end;
end;

var f:text;
	k,n,m:integer;
	a,b,c:TPolynomial;

BEGIN
	
Assign(f,'input.txt');
Reset(f);
ReadLn(f,n);
a := makePolynomial(n);
k := n;
while not Eoln(f) do 
begin
Read(f,a.coeff[k]);
k:=k-1;
end;
ReadLn(f,m);
b := makePolynomial(m);
k := m;
while not Eoln(f) do 
begin
Read(f,b.coeff[k]);
k:=k-1;
end;
WriteLn('Polynomial a');
WriteLn(a.deg);
writePolynomial(a,'x');
WriteLn('Polynomial b');
WriteLn(b.deg);
writePolynomial(b,'x');
c := Karatsuba(a,b);
WriteLn('Polynomial c');
WriteLn(c.deg);
writePolynomial(c,'x');
Close(f);	
END.

Dla pliku tekstowego z danymi

Kopiuj
4
9 7 4 8 9
7
8 4 2 1 6 5 9 4

gdb po załadowaniu i uruchomieniu programu wyświetlił następujący komunikat

Kopiuj

(gdb) r
Starting program: F:\Karatsuba/testKaratsuba
[New Thread 16736.0x5bd0]
[New Thread 16736.0x23c8]
[New Thread 16736.0x6c4]
[New Thread 16736.0x59f0]
Polynomial a
4
+9.000000000000*x^4+7.000000000000*x^3+4.000000000000*x^2+8.000000000000*x^1+9.000000000000*x^0
Polynomial b
7
+8.000000000000*x^7+4.000000000000*x^6+2.000000000000*x^5+1.000000000000*x^4+6.000000000000*x^3+5.000000000000*x^2+9.000000000000*x^1+4.000000000000*x^0
Polynomial c
12
+20.000000000000*x^12+82.000000000000*x^11+92.000000000000*x^10+78.000000000000*x^9+83.000000000000*x^8+163.000000000000*x^7+143.000000000000*x^6+166.000000000000*x^5+176.000000000000*x^4+158.000000000000*x^3+133.000000000000*x^2+113.000000000000*x^1+36.000000000000*x^0
[Inferior 1 (process 16736) exited normally]
(gdb)

Czyli wygląda na to że uruchamia się bez błędów ale zwraca błędny wynik

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
yarel
YA
yarel
YA
  • Rejestracja:prawie 10 lat
  • Ostatnio:około 3 godziny
  • Postów:2367
0

Nie pamiętam już pascala, ale:

  • czy w MakePolynomail nie powinieneś jawnie zerować współczynników wielomianu? Nie wiem, czy w Pascalu jest szansa, że ta tablica będzie zawierać jakieś śmieciowe rzeczy i możesz dostać undefined behaviour.
  • w Karatsuba
Kopiuj
  if ((f.deg = 0)and(f.coeff[0] = 0)) or ((g.deg = 0)and(g.coeff[0] = 0)) then

coeff[0] jest double, więc może powinieneś porównywać numerycznie i mieć funkcję IsZero, która sprawdza czy wartość bezwzględna jest mniejsza niż jakaś ustalona delta (const ZERO = 1e-10;).

  • jakimś cudem wyszedł Ci stopień wielomianu x^12, przy x^7 * x^4 (czyli powinno być x^11) - jeśli nie chcesz bawić się debuggerem, to dodaj sobie najprostsze logowanie i zobacz, w którym miejscu tworzony jest stopień x^12.
N1
Coś musi być nie tak z tym pseudokodem bo właśnie nie powinien wyświetlać stopnia x^12 , a może ja źle wyznaczyłem stopień tych "górnych" części wielomianu a i mam wątpliwości co do poprawności etapu scalania wyników
N1
Ogólnie problem z gościem jest taki że nie ma z nim kontaktu a na komentarze nie odpowiada
YA
Na gotowca nie masz co liczyć. Co Ci mogę zasugerować: 1) Jeśli uważasz, że to problem pseudo kodu, to poszukaj innego opisu algorytmu i porównaj pseudo kod. 2) Spróbuj użyć tego pseudokodu w wersji kartka + ołówek. 3) W implementacji stosuj nazewnictwo zgodne z pseudokodem, czyli np. fu, fl, gu, gl zmaiast tych h1,h2,h3 itp. 4) Podział wielomianu wyodrębnić do osobnej funkcji i to samo z przesuwaniem wielomianu - będzie łatwiej prześledzić kod. 5) Porównaj wersję papier+ołówek z Twoją implementacją.
N1
Ach ta wasza obsesja na punkcie gotowców
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
flowCRANE
flowCRANE
flowCRANE
flowCRANE
Moderator Delphi/Pascal
  • Rejestracja:ponad 13 lat
  • Ostatnio:2 minuty
  • Lokalizacja:Tuchów
  • Postów:12164
1
yarel napisał(a):

Nie wiem, czy w Pascalu jest szansa, że ta tablica będzie zawierać jakieś śmieciowe rzeczy i możesz dostać undefined behaviour.

W Pascalach, zmienne lokalne nie są inicjalizowane automatycznie (a więc zawierają śmieci), natomiast wszystkie zmienne globalne (deklarowane bezpośrednio w module, bez względu na sekcję) oraz wszystkie pola klas są inicjalizowane (zmienne globalne w trakcie inicjalizacji modułu, a pola klas w konstruktorach).

Pracuję nad własną, arcade'ową, docelowo komercyjną grą z gatunku action/adventure w stylu retro (pixel art), programując silnik i powłokę gry od zupełnych podstaw, przy użyciu Free Pascala i SDL3. Więcej informacji znajdziesz na moim mikroblogu.
edytowany 1x, ostatnio: flowCRANE
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Treść
Podgląd
Kliknij, aby dodać treść...
Kliknij, aby dodać załącznik lub wklej ze schowka.
Instrukcja obsługi Markdown
Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)