SORU
2 AĞUSTOS 2009, Pazar


Keyfi hassas aritmetik Açıklaması

Ve ÇOK büyük sayılar (yani, 100 haneli, 1000, vb. basamak) ile çalışmak için yetersizlik rastlamak C öğrenmeye çalışıyorum. Kütüphaneler bunun için var olduğunu biliyorum, ama kendim uygulamaya teşebbüs etmek istiyorum.

Ben sadece eğer biri varsa bilmek istiyorum ya da keyfi kesinlikte aritmetik çok ayrıntılı, evde bir açıklama sağlayabilir.

CEVAP
2 AĞUSTOS 2009, Pazar


Yeterli depolama meselesi ve küçük parçalar olarak sayıları tedavi algoritmaları. Farz edelim bir derleyici olan bir int sadece 0 ile 99 ve istediğiniz tanıtıcı numaraları kadar 999999 (tek endişe pozitif sayılar burada sade ve basit olun).

Her sayı intüç s veren ve (olmalıdır) arka ek için ilköğretim okulunda öğrendim aynı kurallar, çıkarma ve diğer temel işlemleri kullanarak bunu.

Keyfi hassas bir kütüphane, tutabilir sadece temel türler bizim sayıları göstermek için kullanılan, sayısı sabit sınırı yok.

Örneğin ayrıca: 123456 78:

12 34 56
      78
-- -- --
12 35 34

En önemli sondan çalışma:

  • ilk = 0 taşırlar.
  • 56 78 0 1 Ekle = 134 = 34 taşır
  • = 35 = 35 0 34 00 1 taşır
  • 12 00 0 0 carry = 12 = 12 taşırlar

Bu ek genellikle CPU içinde bit düzeyinde nasıl çalıştığını, aslında.

Çıkarma benzer (kullanarak çıkarma tabanı türü ve ödünç yerine taşımak), çarpma yapılabilir tekrarlanan eklemeler (çok yavaş) ya da çapraz ürün (daha hızlı) ve bölünme zor ama yapılabilir çıkıyor ve çıkarma numaraları dahil (uzun bölme olurdu öğrenilen bir çocuk).

Aslında kütüphaneler yazdım(a)bu tür malzeme kullanılarak maksimum güçlerin on olabilir uyum içine bir tamsayı zaman Kare (önlemek için taşma çarparak iki ints birlikte gibi bir 16-bit int sınırlı olmak üzere 0 ile 99 oluşturmak 9,801 (<32,768) kare veya 32-bit int kullanarak 0 ile 9,999 oluşturmak 99,980,001 (<2,147,483,648)) hangi büyük ölçüde hafifletti algoritmaları.

Biraz dikkat et için püf noktaları.

1/ veya rakam ekleyerek çoğalıyor, pre-tahsis en büyük alanı gerekirse çok fazla bulursanız daha sonra azaltmak. Örneğin, iki ekleme 100-"" (burada haneli int) numaraları asla sana 101'den fazla basamak verecektir. basamak 3 haneli bir sayı ile 12 basamaklı bir sayı hiçbir zaman 15'den fazla basamak (basamak sayıları Ekle) oluşturur çarpın.

2/ eklendi hızı normale (depolama için gerekli azaltmak) yalnızca kesinlikle gerekli olduğunda numaraları - kütüphane kullanıcı hız ve depolama endişeleri arasında karar verebilmeniz için ayrı bir çağrı olarak bu vardı.

Pozitif ve negatif bir sayının 3/ ekleme / çıkarma, negatif bir sayı çıkararak olumlu eşdeğer ekleme aynıdır. Ve yöntemleri işaret ayarladıktan sonra birbirlerine çağrı toplama çıkarma sağlayarak kod biraz kaydedebilirsiniz.

4/ değişmez numaraları gibi sonunda bu yana büyük sayılar çıkararak küçük olanlardan Kaçının

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Bunun yerine, 11, inkar sonra: 10 çıkarın

11
10-
--
 1 (then negate to get -1).

İşte bunu yapmak zorundaydım kitaplıkları açıklamalar (metin dönüştü). Kodu kendisi, ne yazık ki, telif hakkına sahiptir, ancak dört temel işlemleri işlemek için yeterli bilgi almak mümkün olabilir. -a -b negatif sayıları temsil etmek ve a b sıfır ya da pozitif bir sayı olduğu aşağıdaki varsayalım.

İçinayrıcaeğer işaretler farklı ise , olumsuzluk çıkarma kullanın:

-a    b becomes b - a
 a   -b becomes a - b

İçinçıkarmaeğer işaretler farklı ise , olumsuzluk olarak kullanın:

 a - -b becomes   a   b
-a -  b becomes -(a   b)

Ayrıca, özel işlem büyük küçük sayılar çıkarma yapıyoruz sağlamak için:

small - big becomes -(big - small)

Çarpmakullanıldığı gibi giriş seviyesi matematik

475(a) x 32(b) = 475 x (30   2)
               = 475 x 30   475 x 2
               = 4750 x 3   475 x 2
               = 4750   4750   4750   475   475

Bu elde böyle bir zamanda 32 (geriye doğru) ekleyin, bir değeri hesaplamak için sonuç (başlangıçta sıfır) eklenecek kullanarak basamak her ayıklama içerir.

ShiftLeft ShiftRight işlemleri hızla çarpmak veya LongInt sar değer bölme (10 "gerçek" matematik) için kullanılır. Yukarıdaki örnekte, 475 sıfır 2 kat ekliyoruz (32 son hanesi) 950 (sonuç = 0 950 = 950)almak için.

Sonra 475 4750 elde etmek için shift 32 3 almak için sağa kayma bıraktık. 4750 14250 almak için 3 tane sıfır ekleyin.

Shift 4750 47500, sağ 0 almak için shift 3 almak için gitti. Doğru 32 değişti artık sıfır olduğu için, işimiz bitti ve aslında 475 x 32 15200 eşit yapar.

Bölümüayrıca zor ama erken aritmetik dayanmaktadır (""yöntem "içine") gider. gazinta, Düşünün 12345 / 27 aşağıdaki uzun bölümü:

       457
    -------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Bu nedenle 12345 / 27 kalan 457 6. Doğrulayın:

  457 x 27   6
= 12339      6
= 12345

Bu düşüşü bir değişken (başlangıçta sıfır) 27 daha büyük veya eşit olana kadar bir zamanda 12345 bir kesimi alaşağı etmek için kullanılarak uygulanır.

O zaman biz 27 - subtractions sayısı segment üst satırı eklenir altına alana kadar sadece 27 çıkarın.

Düşürecek bir daha kesimleri olduğunda, bizim neden var.


Bu temel algoritmalar oldukça dikkat çekiyor. Eğer sayıları özellikle büyük olacak Eğer karmaşık aritmetik yapmak için çok daha iyi yolları vardır. GNU Multiple Precision Arithmetic Library - önemli ölçüde daha iyi ve kendi kütüphaneleri daha hızlı gibi bir şey içine bakabilirsiniz.

Yaptığı bu talihsiz misfeature o olacak sadece çıkış eğer biterse, bellek (oldukça ölümcül hata için genel amaçlı bir kütüphane bence) ama eğer sen-ebilmek bak geçmiş olan, çok iyi görüyor.

Eğer kullanamazsınız bunun için lisans nedeniyle (veya çünkü istemiyorsun uygulama sadece çıkmak için belli bir sebebi yok), hiç olmazsa sen al algoritmaları için entegre içine kendi kodu.

Bu herifleri MPIR (GDP çatal) potansiyel değişiklikleri ile ilgili tartışmalar için daha uygun olduğunu da buldum - geliştirici-dostu bir demet daha fazla görünüyorlar.


(a)Bu, 38**, temelde eğitim amaçlı gibi.

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

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • khloe brooks

    khloe brooks

    25 Temmuz 2011
  • LevelUpTuts

    LevelUpTuts

    20 Ocak 2012
  • xiaoyu85

    xiaoyu85

    20 ŞUBAT 2010