algebramix_doc 0.3
|
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