MOD işlemi, çarpmadan daha fazla CPU mu yoğun?

Question

MOD işlemi neden multiplication'dan biraz daha factor of 2'dan daha pahalı? Lütfen CPU'nun bölünme işlemini nasıl gerçekleştirdiği konusunda daha spesifik olun ve MOD işlemi için sonucu döndürür.

Aşağıdaki örnekte, iş parçacıkları her biri bir saniyeliğine çalışır. Test, bir SPARC işlemcisi üzerinde gerçekleştirildi.

// multiplication 
void someThread() { 

    int a = 10234; 
    while (true) { 
     opers++; 
     a = a * a; 
     a++; 
    } 

    // opers ~ 26 * 10^6 in a sec. 
} 

// MOD 
void someThread() { 

    int a = 10234; 
    while (true) { 
     opers++; 
     a = a % 10000007; 
     a++; 
    } 

    // opers ~ 12 * 10^6 in a sec. 
} 

Answer 1

Algoritma bölünmesi için (işlemciler bölünme ve kapılar uygulanan algoritmalarla çarpma yürütme) çoğalması için daha maliyetlidir. Nitekim, iyi bir karmaşıklığa sahip olan bölüme yönelik bazı algoritmalar, çarpmayı temel bir adım olarak kullanmaktadır.

Okulda öğrenilen naif algoritmaları kullansanız bile. Her ikisi de aynı asimptotik karmaşıklığa sahiptir, fakat bölünmenin sabiti daha büyüktür (rakamı bulmak zorundasınız ve bu önemsiz değildir, bu yüzden dağınıklık yaratabilir ve karışıklığı düzeltmelisiniz).

Answer 2

MOD, bir bölme işlemi değil, bir bölme işlemidir. Bölüm çarpmadan daha pahalıdır. Burada MOD operasyon hakkında

fazla bilgi: o bölünme yoluyla uygulanmaktadır olarak http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

Evet, mod, çarpma daha pahalıdır. (CPU'lar genellikle hem bölümü hem de kalanını bölümlere ayırırlar.) Ancak her iki parçanız da çoğaltma kullanıyor. kopyala/yapıştır hata?

Answer 4

Instruction latencies and throughput for AMD and Intel x86 processors

bir işlem sadece CPU :) de doğal olarak yavaş