zsqr.c - libzahl - big integer library
 (HTM) git clone git://git.suckless.org/libzahl
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) LICENSE
       ---
       zsqr.c (1377B)
       ---
            1 /* See LICENSE file for copyright and license details. */
            2 #include "internals.h"
            3 
            4 
            5 static inline void
            6 zsqr_ll_single_char(z_t a, z_t b)
            7 {
            8         ENSURE_SIZE(a, 1);
            9         a->used = 1;
           10         a->chars[0] = b->chars[0] * b->chars[0];
           11         SET_SIGNUM(a, 1);
           12 }
           13 
           14 void
           15 zsqr_ll(z_t a, z_t b)
           16 {
           17         /*
           18          * Karatsuba algorithm, optimised for equal factors.
           19          */
           20 
           21 #define z2 a
           22         z_t z0, z1, high, low;
           23         zahl_char_t auxchars[3 * ZAHL_FLUFF];
           24         size_t bits;
           25 
           26         bits = zbits(b);
           27 
           28         if (bits <= BITS_PER_CHAR / 2) {
           29                 zsqr_ll_single_char(a, b);
           30                 return;
           31         }
           32 
           33         bits >>= 1;
           34 
           35         /* Try to split only at a character level rather than a bit level.
           36          * Such splits are faster, even if bit-level is required, and do
           37          * not require auxiliary memory except for the bit-level split
           38          * which require constant auxiliary memory. */
           39         if (bits < BITS_PER_CHAR) {
           40                 low->chars = auxchars;
           41                 high->chars = auxchars + ZAHL_FLUFF;
           42                 zsplit_unsigned_fast_small_auto(high, low, b, bits);
           43         } else {
           44                 bits = TRUNCATE_TO_CHAR(bits);
           45                 zsplit_unsigned_fast_large_taint(high, low, b, bits);
           46         }
           47 
           48 
           49         if (unlikely(zzero(low))) {
           50                 zsqr_ll(z2, high);
           51                 zlsh(a, z2, bits << 1);
           52         } else {
           53                 zinit_temp(z0);
           54                 zinit_temp(z1);
           55 
           56                 zsqr_ll(z0, low);
           57 
           58                 zmul_ll(z1, low, high);
           59                 zlsh(z1, z1, bits + 1);
           60 
           61                 zsqr_ll(z2, high);
           62                 zlsh(a, z2, bits << 1);
           63 
           64                 zadd_unsigned_assign(a, z1);
           65                 zadd_unsigned_assign(a, z0);
           66 
           67                 zfree_temp(z1);
           68                 zfree_temp(z0);
           69         }
           70 }