Soru Büyük sayılar nasıl toplanır?


Hesaplamaya çalışıyorum 1 + 1 * 2 + 1 * 2 * 3 + 1 * 2 * 3 * 4 + ... + 1 * 2 * ... * n nerede n kullanıcı girişi. Değerleri için çalışır n 12 ye kadar olan tutarı hesaplamak istiyorum. n = 13, n = 14 ve n = 15. Bunu C89'da nasıl yaparım? Bildiğim kadarıyla kullanabilirim unsigned long long int sadece C99 veya C11'de.

  1. Giriş 13, sonuç 2455009817, beklenen 6749977113
  2. Giriş 14, sonuç 3733955097, beklenen 93928268313
  3. Giriş 15, sonuç 1443297817, beklenen 1401602636313

Kodum:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    unsigned long int n;
    unsigned long int P = 1;
    int i;
    unsigned long int sum = 0;
    scanf("%lu", &n);
    for(i = 1; i <= n; i++)
    {
        P *= i;
        sum += P;
    }
    printf("%lu", sum);
    return 0;
}

32
2018-05-30 10:23


Menşei


GMP gibi harici bir kütüphane kullanmak isteyebilirsiniz.gmplib.org) - Federico klez Culloca
İndirgemeyi anlamıyorum. Gereksinimler açık ve iyi bir örnek verilebilir. - Bathsheba
@Bathsheba: Hiçbir araştırma çabası geçerli bir DV nedenidir. "imzasız uzun menzilli", google veya Wikipedia'da arama terimi kadar uzak değil! - too honest for this site
Tamam, daha büyük ns için bir teknik hazırlıyorum. Bana biraz zaman ver. - Vidor Vistrom
Programınız 64 bit sistemlerde beklenen sonuçları verir. Yani, Windows kullanmıyorsanız. - Edgar Bonet


Cevaplar:


Pratikte, biraz keyfi doğruluk aritmetiği (diğer adıyla. bigint veya bignum) kütüphane. Benim tavsiyem GMPlib ama var diğerleri.

Kendi bignum kütüphanenizi kodlamaya çalışmayın. Verimli ve akıllı algoritmalar vardır, fakat bunlar anlaşılmazdır ve kavramak zordur (bu soruya adanmış bütün kitapları bulabilirsiniz). Ek olarak, GMPlib gibi mevcut kütüphaneler, belirli makine talimatlarından faydalanmaktadır (ör. ADC Standart bir C derleyicinin yaymayacağı (saf C kodundan).

Bu bir ev ödevi ise ve harici kod kullanmanıza izin verilmiyorsa, örneğin bir tabanda bir sayıyı veya kök 1000000000 (bir milyar) ve çocuk olarak öğrendiklerine benzer şekilde çok saf bir şekilde işlemlerinizi kodlayın. Ancak daha etkili algoritmaların (ve gerçek bignum kütüphanelerinin bunları kullandığını) farkında olun.

1000000000 bazında bir dizi bir dizi ile temsil edilebilir. unsignedHer biri 1000000000 tabanının "rakamı" dır. Bu yüzden dizileri yönetmeniz gerekir (büyük olasılıkla malloc) ve uzunlukları.


88
2018-05-30 10:32



Burada bazı iyi tavsiyeler. Reddini anlamadım, Tersine çevirme zamanı! - Bathsheba
@chtz: "BN kütüphanesinin yorumlanmış bir dilde uygulanıp uygulanmayacağını bilmiyorum." - Bu tamamen konu dışı, ama bir ara bir kez, konu dışı eğlenceli olabiliriz. Modern yüksek performanslı dinamik optimize ediciler son derece olmayan sezgisel. Örneğin, PSD'leri (Photoshop dosyaları) işlemek için bir Ruby gem var. Yüksek düzeyde optimize edilmiş bir C uzantısı (bunları destekleyen Ruby uygulamaları için) ve saf, deyimsel Ruby'de "geri dönüş" uygulaması olarak (örneğin AOT-derleyici olan Topaz gibi C uzantılarını desteklemeyen uygulamalar için) uygulanır. ... - Jörg W Mittag
… ECMAScript). Ve bu saf Yakut geri dönüş uygulaması, optimize edilmeye karşı direnmeyi hayal edebileceğiniz neredeyse her şeyi yapar. Örneğin. Çalışma zamanı dizeleri ve benzeri şeylerde saklanan yöntem adlarından dinamik olarak yöntemleri çağırmak. Bir dizi metot isminin üzerine gelmek ve onları çağırmak için yansıtıcı. Yani, bunun muhtemelen hızlı olamayacağını düşünebilirsiniz. Ama, işte buradaki kicker: Kesinlikle Çünkü Ruby'de yazılmıştır, TruffleRuby en iyi yorumlayıcı tercümanı, çok sayıda inline, uzmanlaşma ve optimizasyon turu ile tüm test programını bir sabit olarak sabitleyebilir! Bu … - Jörg W Mittag
Ruby-C-bariyerini geçmek maliyetli olduğundan, C uzantısını kullanmaktan önemli ölçüde daha hızlıdır. TruffleRuby, test programı (Ruby'de yazılmış), PSD kütüphanesi (Ruby'de yazılmış) ve Ruby çekirdek veri yapıları (Ruby'de yazılmış) arasında ileri ve geri hareket ederken, YARV'nin şu şekilde çalışacak hiçbir şeyi yoktur: YARV sadece Ruby'yi nasıl çalıştıracağını bilir hızlı, ama kodun Ruby kısmı önemsiz. YARV'in Ruby çekirdek veri yapıları (C dilinde yazılmış) veya PSD kütüphanesi (C ile yazılmış) hakkında bir fikri yoktur. GCC, Ruby kodunu optimize edemediği için optimize edemez. Ve Ruby'den her çağrıya… - Jörg W Mittag
… PSD kütüphanesi, VM sınırının pahalı geçişidir. Sonunda, bu çapraz dil çağrılarını ortadan kaldırmak, her şeyi geri almanızı ve Ruby'deki hesaplama yoğun kodunu yazmanızdan kaybettiğinizden daha fazlasını elde etmenizi sağlar. Yani, "yorumlanmış bir dilde bir BN kütüphanesi uygulamak" olduğuna inanmıyorum o çirkin. Hesaplama-yoğun kodun daha büyük bir uygulama içine inline edilebilme yeteneği göz ardı edilmemelidir. - Jörg W Mittag


Sen kullanabilirsin doubleÖzellikle platformunuz IEEE754 kullanıyorsa.

Böyle bir double size 53 bit hassasiyet verir, yani tamsayılar tam olarak 53'üncü gücüne kadar gelir. Bu durum için yeterince iyi.

Platformunuz IEEE754'ü kullanmıyorsa, benimsenen kayan noktalı şemadaki belgelere başvurun. O belki yeterli ol


20
2018-05-30 10:25



Evet, çiftle çalışıyor. Teşekkür ederim! - Timʘtei
Bir BigInt çözümünün aksine, bunun belirli bir noktanın ötesinde kesinliği kaybedeceğini unutmayın. - BallpointBen
Aslında. IEEE754 için 2'nin 53. iktidarından sonra. Ama böylece entegre tiplerde inşa edilecek. Yani işiniz için doğru tipi seçmeniz gerekiyor. - Bathsheba


MaxInt limitinin üzerindeyken basit bir yaklaşım, uygun bir n için modulo 10 ^ n hesaplamaları yapmaktır ve kayan nokta hesaplaması ile aynı hesaplama yaparsınız fakat her şeyi 10 ^ r'ye bölerseniz. İlk n hanelerini size verirken, ikinci sonuç size ilk r basamağının kaldırılmasıyla cevabın son basamağını verecektir. Daha sonra, son birkaç basamak, yuvarlama hataları nedeniyle hatalı olacaktır, bu yüzden n'yi n'den biraz daha küçük seçmelisiniz. Bu durumda n = 9 ve r = 5 almak iyi çalışır.


0
2018-05-30 23:20