SORU
2 NİSAN 2010, Cuma


Hızlı bir şekilde hesaplamak için 128-bit tamsayı modül bir 64-bit tamsayı

Ben bir 128-bit işaretsiz tamsayı bir 64-bit işaretsiz tamsayı B. en hızlı yolu hesaplamak için A % B - (64-bit) bir paranın, Bir bölünme ile B?

C veya assembly dilinde bunu yapmak için arıyorum, ama 32-bit x 86 platformu hedef lazım. Bu ne yazık ki, ne x 64 mimarisi tek bir talimat gerekli işlemi gerçekleştirmek için yeteneği 128-bit tamsayı için derleyici desteği yararlanmak, yapamam anlamına gelir.

Düzenleme:

Cevapları gerçekten çok teşekkür ederim. Ancak göründüğü için bana önerilen algoritmalar olurdu oldukça yavaş olmaz en hızlı şekilde gerçekleştirmek için bir 128-bit ile 64-bit bölümü için kaldıraç işlemcinin yerel destek için 64-bit ile 32-bit bölüm? Eğer birkaç küçük bölümler açısından büyük bölünme gerçekleştirmek için bir yol olup olmadığını biliyor mu?

Ynt: Ne sıklıkla B değiştiriyor?

Öncelikle genel bir çözüm ilgileniyorum - ne hesaplama eğer A ve B her seferinde farklı olması muhtemeldir eğer gerçekleştirmek istiyorsunuz?

Ancak, ikinci bir olası durum B olarak A - 200 kadar olabilir her B. tarafından bölmek Gibi değişmez olduğunu Nasıl cevap bu durumda bir farkı olur?

CEVAP
2 NİSAN 2010, Cuma


Russian Peasant Multiplication bölümü sürümünü kullanabilirsiniz.

Kalanı bulmak için, yürütme (pseudo-code):

X = B;

while (X < A/2)
{
    X <<= 1;
}

while (A >= B)
{
    if (A >= X)
        A -= X;
    X >>= 1;
}

Modül A. bırakılır

Vardiya, karşılaştırmalar ve subtractions değerleri 64 bit numaraları bir çift oluşan ameliyat için uygulamak gerekir, ama bu oldukça önemsiz.

Bu 254 kez (128 bit ile en döngü. Elbette pre-check sıfır bölen için yapmanız gereken.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Awesomesauce Network

    Awesomesauce

    4 EKİM 2012
  • Jon Reed

    Jon Reed

    14 AĞUSTOS 2006
  • RiverCityGraphix

    RiverCityGra

    6 Ocak 2012