algebramix_doc 0.3
/Users/mourrain/Devel/mmx/algebramix/src/matrix_integer.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : matrix_integer.cpp
00004 * DESCRIPTION: Multi-modular multiplication of integer matrices
00005 * COPYRIGHT  : (C) 2008  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license and comes WITHOUT
00008 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00009 * If you don't have this file, write to the Free Software Foundation, Inc.,
00010 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00011 ******************************************************************************/
00012 
00013 #include <numerix/integer.hpp>
00014 
00015 namespace mmx {
00016 
00017 xnat
00018 matrix_product_bit_size (const integer* s1, nat s1_rs, nat s1_cs,
00019                          const integer* s2, nat s2_rs, nat s2_cs,
00020                          nat r, nat l, nat c)
00021 {
00022   double count= 1.0;
00023   xnat   sz   = 0;
00024   // NOTE: the largest integer in the result will be bounded by
00025   // count * 2^sz at the end. The bound is computed carefully,
00026   // so as to be both fast and relatively sharp.
00027   for (nat k=0; k<l; k++) {
00028     xnat sz1= 0, sz2= 0;
00029     const integer* ss1= s1 + k * s1_cs;
00030     const integer* ss2= s2 + k * s2_rs;
00031     for (nat i=0; i<r; i++, ss1 += s1_rs)
00032       sz1= max (sz1, bit_size (*ss1));
00033     for (nat j=0; j<c; j++, ss2 += s2_cs)
00034       sz2= max (sz2, bit_size (*ss2));
00035     xnat szs= sz1 + sz2;
00036     if (szs > sz) {
00037       if (szs >= sz + 30) {
00038         count= (count / 1.0e9) + 1.000000001;
00039         sz   = szs;
00040       }
00041       else {
00042         count= (count / ((double) (1 << (szs - sz)))) + 1.000000001;
00043         sz   = szs;
00044       }
00045     }
00046     else {
00047       if (sz >= szs + 30) count += 1.0e-9;
00048       else count += 1.000000001 / ((double) (1 << (sz - szs)));
00049     }
00050   }
00051   return sz + ((xnat) logb (count)) + 1;
00052 }
00053 
00054 } // namespace mmx
 All Classes Namespaces Files Functions Variables Typedefs Friends Defines