Newton-Raphson Bölümü

Question

Programlama alıştırması olarak BigInt sınıfı yapıyorum. Base-65536'da 2'nin tamamlanmış imzalı bir vektörünü kullanır (böylece 32 bitlik çarpımlar taşmaz. Tamamen çalıştıktan sonra tabanı arttıracağım).

Temel matematik işlemlerinin tümü tek bir sorunla kodlanmıştır: bölüm, ağrısız oluşturmak için temel algoritma ile yavaştır. (Bölümün her basamağı için ikili bölüm gibi çalışır ... Birisi onu görmek istemedikçe onu yayınlamayacağım ....)

Yavaş algoritmam yerine kullanmak istiyorum Newton-Raphson (değişmiş) karşılıklı ve sonra çoğaltır (ve kaydırır). Sanırım kafamın temelleri var: formülünü (x1 = x0 (2 - x0 * bölen)) iyi bir başlangıç ​​tahminini verdikten sonra, bir miktar yinelemeden sonra, x karşılıklı olarak birleşir. Bu bölüm yeterince kolay görünüyor ... ama büyük tamsayılar için bu formülü uygulamak çalışırken bazı sorunlarla çalıştırıyorum:

Sorun 1:

Ben tamsayılar ile çalışıyorum Çünkü ... iyi .. Kesirleri kullanamıyorum. Bu x'in daima farklılaşmasına neden olur (x0 * bölücü < 2 olmalı?). Sezgim bana, tamsayı (bazı doğrulukta) çalışmasına izin verecek olan denklemde bir değişiklik yapılması gerektiğini söyler ama ben gerçekten ne olduğunu bulmak için uğraşıyorum. (Benim matematik becerilerimden yoksunum beni burada yeniyor ....) Bence d yerine d * [base^somePower] nerede eşdeğer bir denklem bulmalıyım? Bütün sayılarla çalışan (x1 = x0 (2 - x0 * d)) gibi bir denklem olabilir mi?

Sorun 2:

Bazı sayıların devrik bulmak için Newton'un formülü kullanabilirsiniz, sonuç cevap ne olması gerektiği aşağıda sadece küçük hizip ... ex olmak biter. (Ondalık) 4 devrik bulunmaya çalışılırken:

x0 = 0.3 
x1 = 0.24 
x2 = 0.2496 
x3 = 0.24999936 
x4 = 0.2499999999983616 
x5 = 0.24999999999999999999998926258176 

Ben tabanına-10 sayı temsil olsaydı, ben 25 bir sonuç isteyeyim (ve 2 tarafından sağ shift ürüne hatırlamak). 1/3 gibi bazı karşılıklı ilişkilerde, yeterli doğruluğa sahip olduğunuzu öğrendikten sonra sonucu kısaltabilirsiniz. Fakat yukarıdaki sonuçtan doğru olanı nasıl çıkarabilirim?

Eğer bu çok muğlaksa ya da çok fazla istesem özür dilerim. Vikipedi ve Google'da bulabildiğim tüm araştırma makalelerini inceledim, ama sanırım kafamı duvara çarpıyormuş gibi hissediyorum. Herkesin bana verebileceği herhangi bir yardım için minnettarım!

...

Düzenleme: beklediğimden çok daha yavaş olmasına rağmen, algoritma çalışma var. Eski algoritmamla kıyaslandığında çok fazla hız kaybettim, hatta binlerce rakamı olan sayılarda bile ... Hala bir şeyi özlüyorum. Çok hızlı olan çarpma ile ilgili bir sorun değil. (Gerçekten Karatsuba'nın algoritmasını kullanıyorum).ilgilenen herkes için

, burada Newton Raphson algoritması benim şimdiki yineleme:

bigint operator/(const bigint& lhs, const bigint& rhs) { 
    if (rhs == 0) throw overflow_error("Divide by zero exception"); 
    bigint dividend = lhs; 
    bigint divisor = rhs; 

    bool negative = 0; 
    if (dividend < 0) { 
     negative = !negative; 
     dividend.invert(); 
    } 
    if (divisor < 0) { 
     negative = !negative; 
     divisor.invert(); 
    } 

    int k = dividend.numBits() + divisor.numBits(); 
    bigint pow2 = 1; 
    pow2 <<= k + 1; 

    bigint x = dividend - divisor; 
    bigint lastx = 0; 
    bigint lastlastx = 0; 
    while (1) { 
     x = (x * (pow2 - x * divisor)) >> k; 
     if (x == lastx || x == lastlastx) break; 
     lastlastx = lastx; 
     lastx = x; 
    } 
    bigint quotient = dividend * x >> k; 
    if (dividend - (quotient * divisor) >= divisor) quotient++; 
    if (negative)quotient.invert(); 
    return quotient; 
} 

Ve burada daha hızlıdır benim (gerçekten çirkin) eski algoritmasıdır:

bigint operator/(const bigint& lhs, const bigint & rhs) { 
    if (rhs == 0) throw overflow_error("Divide by zero exception"); 
    bigint dividend = lhs; 
    bigint divisor = rhs; 

    bool negative = 0; 
    if (dividend < 0) { 
     negative = !negative; 
     dividend.invert(); 
    } 
    if (divisor < 0) { 
     negative = !negative; 
     divisor.invert(); 
    } 

    bigint remainder = 0; 
    bigint quotient = 0; 
    while (dividend.value.size() > 0) { 
     remainder.value.insert(remainder.value.begin(), dividend.value.at(dividend.value.size() - 1)); 
     remainder.value.push_back(0); 
     remainder.unPad(); 
     dividend.value.pop_back(); 

     if (divisor > remainder) { 
      quotient.value.push_back(0); 
     } else { 
      int count = 0; 
      int i = MSB; 
      bigint value = 0; 
      while (i > 0) { 
       bigint increase = divisor * i; 
       bigint next = value + increase; 
       if (next <= remainder) { 
        value = next; 
        count += i; 
       } 
       i >>= 1; 
      } 
      quotient.value.push_back(count); 
      remainder -= value; 
     } 
    } 

    for (int i = 0; i < quotient.value.size()/2; i++) { 
     int swap = quotient.value.at(i); 
     quotient.value.at(i) = quotient.value.at((quotient.value.size() - 1) - i); 
     quotient.value.at(quotient.value.size() - 1 - i) = swap; 
    } 

    if (negative)quotient.invert(); 
    quotient.unPad(); 
    return quotient; 
} 

Answer 1

Her şeyden önce, zaman dilimini O(n^2) zamanında ve makul bir sabitle uygulayabilirsiniz, bu nedenle bu sayısız çarpımdan (çok) yavaş olmaz. Ancak, Karatsuba benzeri algoritma veya FFT tabanlı çoğaltma algoritması kullanırsanız, o zaman Newton-Raphson'u kullanarak bölünme algoritmanızı hızlandırabilirsiniz. x devrik hesaplanması için

bir Newton-Raphson yineleme q[n+1]=q[n]*(2-q[n]*x) olup.

B'un pozitif bir tamsayı olduğu floor(2^k/B) hesaplamak istediğimizi varsayalım. WLOG, B≤2^k; aksi halde, bölüm 0'dur. x=B/2^k için Newton-Raphson yineleme, q[n+1]=q[n]*(2-q[n]*B/2^k) verir. Bu tip her yineleme sadece tamsayı çarpma ve bit vardiya gerektirir

q[n+1]=q[n]*(2^(k+1)-q[n]*B) >> k

olarak yeniden düzenleyebilirsiniz. floor(2^k/B) mu? Şart değil. Ancak, en kötü durumda, sonunda floor(2^k/B) ve ceiling(2^k/B) (Prove it!) Arasında değişmektedir. Yani, bu durumda olup olmadığınızı görmek için çok zahmetsiz bir test kullanabilirsiniz ve floor(2^k/B)'u çıkarın. (Bu "o kadar da zekice olmayan test", her bir yinelemede çarpımlardan daha hızlı olmalıdır, ancak bu şeyi optimize etmek iyi olacaktır). Gerçekten de, A,B herhangi bir pozitif tamsayı için floor(A/B) hesaplamak için floor(2^k/B)10 hesaplanması yeterlidir. k'u A*B≤2^k yapın ve floor(A/B)=A*ceiling(2^k/B) >> k'u doğrulayın. Son olarak, bu yaklaşım için basit ama önemli bir optimizasyon, Newton-Raphson yönteminin erken iterasyonlarında çoğulları (yani, sadece ürünün daha yüksek bitlerini hesaplar) kesmektir. Bunu yapmanın nedeni, erken iterasyonların sonuçlarının bölümden uzak olması ve bunları yanlış bir şekilde gerçekleştirmenin önemli olmadığıdır. (Bu argümanı daraltın ve bu şeyi uygun bir şekilde yaparsanız, O(M(2n)) zamanında iki ≤n-bit tamsayılarını bölebilirsiniz, bu nedenle iki ≤k-bit tam sayıyı M(k) zamanında ve M(x) artan bir dışbükey işlevdir).

Answer 2

Newton- Raphson, bir tamsayı algoritmasıdır - tamsayı matematikte kullanım için uygun değildir. Gördüğünüz sorunlara yol açacak yuvarlama hataları alacaksınız. Kayan nokta sayıları ile ilgili problemi çözebilir ve daha sonra belirli bir sayıya kadar bir tamsayı elde edip edemeyeceğinizi görebilirsiniz (bkz. Bir sonraki paragraf)

İkinci problem hakkında, bir kesinlik (ondalık basamak sayısı) seçin. Doğruluk ve doğruluk için istediğiniz kadar. Eğer sorunda yirmi haneli bir hassasiyet seçtiyseniz, 0,25'e varacaksınız. Sadece gerekli olan rakamlar sabit olana kadar yinelemeniz gerekir. Genelde, bir bilgisayardaki irrasyonel sayıları temsil etmek genellikle uygunsuzluk getirir.

Answer 3

Bunu doğru görürsem önemli bir gelişme x için iyi bir başlangıç ​​değeri seçmektir.

1/x = pow(2,log2(1/x)) 
1/x = pow(2,-log2(x)) 
1/x >= pow(2,-floor(log2(x))) 

kat olarak, bölen sen tersin en önemli bit olmak zorunda nerede olduğunu kaç basamak bilerek (log2 (x)) sadece en anlamlı bit kümesinin endeksidir.