1
2 /*
3 * Integer - Implements an integer of arbitrary size
4 * Copyright (c) 2005-2007 by Mattias Hultgren <tilda_o_tize@hotmail.com>
5 *
6 * See integer.h
7 */
8
9
10 #include "integer.h"
11 #include "keyfile.h"
12 #include <math.h>
13 #include <stdio.h>
14 #include <string.h>
15
16
17
append_to_string(utf8_string & str,uint32 nrofdigits) const18 void Integer::append_to_string( utf8_string &str, uint32 nrofdigits ) const throw(error_obj)
19 {
20 utf8_string str1(""), str2(""), *ptr, *ptr2, *tmp_ptr;
21 Integer nr, rest, divider, tmp;
22 char char_str[25];
23
24 divider = int64(1000000000)*int64(1000000000);
25
26 ptr = &str1;
27 ptr2 = &str2;
28 if( used == 0 )
29 str1 = "0";
30 else
31 {
32 if( used >= 5 )
33 {
34 uint32 rest_digits;
35
36 rest = int32( float((used-1)/4 +1)*1.07 );
37 rest_digits = rest.data[0]*18;
38
39 divider.power( rest, &tmp );
40 this->divide( tmp, &nr, &rest );
41 rest.negative = false;
42
43 if( nrofdigits < rest_digits )
44 nr.append_to_string( str );
45 else
46 nr.append_to_string( str, nrofdigits - rest_digits );
47 rest.append_to_string( str, rest_digits );
48 return;
49 }
50 else
51 {
52 nr = *this;
53
54 do
55 {
56 nr.divide( divider, &tmp, &rest );
57 nr.swap( tmp );
58
59 if( nr == 0 )
60 {
61 if( rest.used == 1 )
62 uint64_to_char( uint64(rest.data[0]), char_str );
63 else
64 uint64_to_char( uint64(rest.data[0])+(uint64(rest.data[1])<<32), char_str );
65 }
66 else
67 {
68 if( rest.used == 0 )
69 uint64_to_char( uint64(0), char_str, 18 );
70 else if( rest.used == 1 )
71 uint64_to_char( uint64(rest.data[0]), char_str, 18 );
72 else
73 uint64_to_char( uint64(rest.data[0]) + (uint64(rest.data[1])<<32), char_str, 18 );
74 }
75 tmp_ptr = ptr;
76 ptr = ptr2;
77 ptr2 = tmp_ptr;
78
79 *ptr = char_str;
80 ptr->append( *ptr2 );
81 }while( nr != 0 );
82
83 if( negative )
84 {
85 tmp_ptr = ptr;
86 ptr = ptr2;
87 ptr2 = tmp_ptr;
88
89 *ptr = "-";
90 ptr->append( *ptr2 );
91 }
92 }
93 }
94
95 if( ptr->test_character( 0, "-" ) == false )
96 {
97 if( ptr->get_length() < nrofdigits ) // the number of digit is not met,
98 { // lets add some starting zero's
99 tmp_ptr = ptr;
100 ptr = ptr2;
101 ptr2 = tmp_ptr;
102
103 *ptr = "";
104 while( ptr2->get_length() < nrofdigits )
105 {
106 nrofdigits--;
107 ptr->append( "0" );
108 }
109 ptr->append( *ptr2 );
110 }
111 }
112
113 str.append( *ptr );
114 }
115
116 // gcd - greatest common divisior (using Euklides algorithm)
117 // if any of nr1 & nr2 is zero the return value is zero also
gcd(Integer nr1,Integer nr2)118 Integer gcd( Integer nr1, Integer nr2 ) throw(error_obj)
119 {
120 if( nr1.used == 0 )
121 return nr2;
122 if( nr2.used == 0 )
123 return nr1;
124
125 if( nr1.negative )
126 nr1.negate();
127 if( nr2.negative )
128 nr2.negate();
129
130 {
131 Integer tmp;
132
133 if(nr2 > nr1) // this makes nr1 to be the largest number
134 goto gcd_nr2_is_bigger;
135 for(;;)
136 {
137 nr1.divide( nr2, 0, &tmp );
138 if(tmp.used == 0)
139 return nr2;
140 nr1.swap( tmp );
141
142 gcd_nr2_is_bigger:
143 nr2.divide( nr1, 0, &tmp );
144 if(tmp.used == 0)
145 return nr1;
146 nr2.swap( tmp );
147 }
148 }
149 }
150 // lcm - least common multiple ( (nr1*nr2)/gcd(nr1,nr2) )
151 // if(gcd(nr1,nr2) == 0) the return value is zero also
lcm(const Integer & nr1,const Integer & nr2)152 Integer lcm( const Integer &nr1, const Integer &nr2 ) throw(error_obj)
153 {
154 Integer tmp;
155
156 tmp = gcd(nr1,nr2);
157 if(tmp == 0)
158 return 0;
159
160 return (nr1 / tmp) * nr2;
161 }
162
Integer(floatx src)163 Integer::Integer(floatx src) throw(error_obj)
164 {
165 uint32 i;
166 floatx tmp,tmp2;
167
168 negative = false;
169 size = 0;
170 used = 0;
171 data = 0;
172
173 if( src <= -1.0 )
174 size = uint32( (log2x( -src ) + 1.0) / 32.0 ) + 1;
175 else if( src < 1.0 && src > -1.0 )
176 {
177 size = 0;
178 return;
179 }
180 else
181 size = uint32( (log2x( src ) + 1.0) / 32.0 ) + 1;
182
183 if( size > 2 )
184 {
185 try{ data = new uint32[size]; }
186 catch(...) { THROW_ERROR( ErrorType_Memory, _("Couldn't get memory.") ); }
187 }
188 else
189 data = buf;
190
191 used = size;
192 if( src < 0.0 )
193 {
194 negative = true;
195 src = -src;
196 }
197 src = truncx( src );
198
199 for( i=1; i<=size; i++ )
200 {
201 if( size == i )
202 tmp2 = truncx(src);
203 else
204 {
205 tmp = powx( (floatx(uint32_max)+1.0), floatx(size-i) );
206
207 tmp2 = truncx(src/tmp);
208 }
209 data[size-i] = uint32( tmp2 );
210
211 src = truncx( src - tmp2*tmp );
212 }
213
214 if( data[used-1] == 0 )
215 used--;
216 }
operator floatx(void)217 Integer::operator floatx(void)
218 {
219 floatx res;
220
221 switch( used )
222 {
223 case 0:
224 return 0.0;
225
226 case 1:
227 res = floatx( *data );
228 break;
229
230 default:
231 res = 0.0;
232 for( uint32 i=0; i < used && i < 3 ; i++ )
233 res += floatx(data[used-i-1]) * powx( float(uint32_max)+1.0f, floatx(used-i-1) );
234 }
235
236 if( negative )
237 return -res;
238 return res;
239 }
operator =(floatx val)240 Integer & Integer::operator=(floatx val) throw(error_obj)
241 {
242 uint32 i, new_size;
243 floatx tmp,tmp2;
244
245 if( val <= -1.0 )
246 new_size = uint32( (log2x( -val ) + 1.0) / 32.0 ) + 1;
247 else if( val < 1.0 && val > -1.0 )
248 {
249 used = 0;
250 return *this;
251 }
252 else
253 new_size = uint32( (log2x( val ) + 1.0) / 32.0 ) + 1;
254
255 if( new_size > size )
256 {
257 if( size > 2 )
258 delete [] data;
259 data = 0;
260 used = 0;
261 size = 0;
262
263 if( new_size > 2 )
264 {
265 try{ data = new uint32[new_size]; }
266 catch(...) { THROW_ERROR( ErrorType_Memory, _("Couldn't get memory.") ); }
267 }
268 else
269 data = buf;
270
271 size = new_size;
272 }
273
274 used = new_size;
275 if( val < 0.0 )
276 {
277 negative = true;
278 val = -val;
279 }
280 val = truncx( val );
281
282 for( i=1; i<=new_size; i++ )
283 {
284 if( new_size == i )
285 tmp2 = truncx(val);
286 else
287 {
288 tmp = powx( (floatx(uint32_max)+1.0), floatx(new_size-i) );
289
290 tmp2 = truncx(val/tmp);
291 }
292 data[new_size-i] = uint32( tmp2 );
293
294 val = truncx( val - tmp2*tmp );
295 }
296
297 if( data[used-1] == 0 )
298 used--;
299 return *this;
300 }
301
302
303
304
Integer()305 Integer::Integer()
306 {
307 negative = false;
308 size = 0;
309 data = 0;
310 used = 0;
311 }
312
Integer(const Integer & src)313 Integer::Integer( const Integer &src ) throw(error_obj)
314 {
315 negative = false;
316 size = 0;
317 used = 0;
318 data = 0;
319
320 this->operator=( src );
321 }
322
Integer(int32 src)323 Integer::Integer(int32 src)
324 {
325 negative = false;
326 size = 0;
327 used = 0;
328 data = 0;
329
330 if( src == 0 )
331 return;
332
333 data = buf;
334
335 size = 1;
336 used = 1;
337 if( src < 0 )
338 {
339 negative = true;
340 data[0] = uint32( -src );
341 }
342 else
343 {
344 negative = false;
345 data[0] = uint32( src );
346 }
347 }
348
Integer(int64 src)349 Integer::Integer(int64 src)
350 {
351 negative = false;
352 size = 0;
353 used = 0;
354 data = 0;
355
356 if( src == 0 )
357 return;
358
359 data = buf;
360
361 size = 2;
362 used = 2;
363
364 if( src < 0 )
365 {
366 negative = true;
367 data[1] = uint32( uint64(-src) >> 32 );
368 data[0] = uint32( uint64(-src) );
369 }
370 else
371 {
372 negative = false;
373 data[1] = uint32( uint64(src) >> 32 );
374 data[0] = uint32( uint64(src) );
375 }
376 if( data[1] == 0 )
377 used = 1;
378 }
379
~Integer()380 Integer::~Integer()
381 {
382 if( size > 2 )
383 delete [] data;
384 }
385
operator int64(void)386 Integer::operator int64(void)
387 {
388 int64 res;
389
390 if( used == 0 )
391 return int64(0);
392
393 if( used >= 3 )
394 res = int64_max;
395 else
396 {
397 res = data[0];
398
399 if( used == 2 )
400 {
401 if( data[1] >= (uint32(1)<<31) )
402 res = int64_max;
403 else
404 res += int64(data[1])*(int64(1)<<32);
405 }
406 }
407
408 if( negative )
409 return -res;
410 return res;
411 }
412
operator =(int32 src)413 Integer & Integer::operator=(int32 src)
414 {
415 if( src == 0 )
416 {
417 used = 0;
418 return *this;
419 }
420
421 enlarge_to( 1 );
422
423 used = 1;
424 if( src < 0 )
425 {
426 negative = true;
427 data[0] = uint32( -src );
428 }
429 else
430 {
431 negative = false;
432 data[0] = uint32( src );
433 }
434 return *this;
435 }
436
operator =(int64 src)437 Integer & Integer::operator=(int64 src)
438 {
439 if( src == 0 )
440 {
441 used = 0;
442 return *this;
443 }
444
445 enlarge_to( 2 );
446
447 used = 2;
448
449 if( src < 0 )
450 {
451 negative = true;
452 data[1] = uint32( uint64(-src) >> 32 );
453 data[0] = uint32( uint64(-src) );
454 }
455 else
456 {
457 negative = false;
458 data[1] = uint32( uint64(src) >> 32 );
459 data[0] = uint32( uint64(src) );
460 }
461 if( data[1] == 0 )
462 used = 1;
463
464 return *this;
465 }
466
operator =(const Integer & val)467 Integer & Integer::operator=(const Integer &val) throw(error_obj)
468 {
469 if( size < val.used )
470 {
471 if( size > 2 )
472 delete [] data;
473 size = 0;
474 used = 0;
475 data = 0;
476
477 if( val.used > 2 )
478 {
479 try{ data = new uint32[val.used]; }
480 catch(...) { THROW_ERROR( ErrorType_Memory, _("Couldn't get memory.") ); }
481 }
482 else
483 data = buf;
484
485 size = val.used;
486 }
487 used = val.used;
488 negative = val.negative;
489
490 for( uint32 i=0; i<used; i++ )
491 data[i] = val.data[i];
492
493 return *this;
494 }
495
operator ==(const Integer & val) const496 bool Integer::operator==(const Integer &val) const
497 {
498 if( used != val.used )
499 return false;
500 if( used == 0 )
501 return true;
502
503 if( negative != val.negative )
504 return false;
505
506 for( uint32 i=0; i<used; i++ )
507 {
508 if( data[i] != val.data[i] )
509 return false;
510 }
511 return true;
512 }
513
operator ==(int32 val) const514 bool Integer::operator==(int32 val) const
515 {
516 uint32 tmp;
517
518 if( used == 0 )
519 return (val == 0);
520
521 if( used > 1 )
522 return false;
523
524 if( negative )
525 {
526 if( val < 0 )
527 tmp = uint32(-int64(val));
528 else
529 return false;
530 }
531 else
532 {
533 if( val < 0 )
534 return false;
535 tmp = uint32(val);
536 }
537
538 return ( data[0] == tmp );
539 }
540
541 // -1 this is smaller
542 // 0 they are equal
543 // 1 this is bigger
compare_abs_value(const Integer & val) const544 int Integer::compare_abs_value( const Integer &val ) const
545 {
546 if( used == 0 )
547 {
548 if( val.used == 0 )
549 return 0;
550 return -1;
551 }
552
553 if( used < val.used )
554 return -1;
555 if( used > val.used )
556 return 1;
557
558 for( uint32 i=used; i>0; i-- )
559 {
560 if( data[i-1] != val.data[i-1] )
561 return ( data[i-1] < val.data[i-1] ) ? -1 : 1;
562 }
563 return 0;
564 }
565
compare_abs_value_shifted(const Integer & val,uint32 shift) const566 int Integer::compare_abs_value_shifted( const Integer &val, uint32 shift ) const
567 {
568 uint32 i;
569 if( used == 0 )
570 {
571 if( val.used == 0 )
572 return 0;
573 return -1;
574 }
575 if( val.used == 0 )
576 return 1;
577
578 if( used < (val.used+shift) )
579 return -1;
580 if( used > (val.used+shift) )
581 return 1;
582
583 for( i=used; i>shift; i-- )
584 {
585 if( data[i-1] != val.data[i-shift-1] )
586 return ( data[i-1] < val.data[i-shift-1] ) ? -1 : 1;
587 }
588 for( ; i>0; i-- )
589 {
590 if( data[i-1] != 0 )
591 return 1;
592 }
593 return 0;
594 }
595
operator <(const Integer & val) const596 bool Integer::operator<(const Integer &val) const
597 {
598 if( used == 0 )
599 {
600 if( val.used == 0 )
601 return false;
602
603 return !val.negative;
604 }
605
606 if( negative != val.negative )
607 return negative;
608
609 if( used < val.used )
610 return !negative;
611 if( used > val.used )
612 return negative;
613
614 for( uint32 i=used; i>0; i-- )
615 {
616 if( data[i-1] != val.data[i-1] )
617 {
618 if( negative )
619 return ( data[i-1] > val.data[i-1] );
620 return ( data[i-1] < val.data[i-1] );
621 }
622 }
623
624 return false;
625 }
626
operator <(int32 val) const627 bool Integer::operator<(int32 val) const
628 {
629 uint32 tmp;
630
631 if( used == 0 )
632 {
633 if( val == 0 )
634 return false;
635
636 return (val > 0);
637 }
638
639 if( negative != (val < 0) )
640 return negative;
641
642 if( used > 1 )
643 return false;
644
645 if( val < 0 )
646 tmp = uint32( (-int64(val))+int64(1) );
647 else
648 tmp = uint32(val);
649
650 if( negative )
651 return ( data[0] > tmp );
652 return ( data[0] < tmp );
653 }
654
operator >(const Integer & val) const655 bool Integer::operator>(const Integer &val) const
656 {
657 if( used == 0 )
658 {
659 if( val.used == 0 )
660 return false;
661
662 return val.negative;
663 }
664
665 if( negative != val.negative )
666 return !negative;
667
668 if( used < val.used )
669 return negative;
670 if( used > val.used )
671 return !negative;
672
673 for( uint32 i=used; i>0; i-- )
674 {
675 if( data[i-1] != val.data[i-1] )
676 {
677 if( negative )
678 return ( data[i-1] < val.data[i-1] );
679 return ( data[i-1] > val.data[i-1] );
680 }
681 }
682
683 return false;
684 }
685
operator >(int32 val) const686 bool Integer::operator>(int32 val) const
687 {
688 uint32 tmp;
689
690 if( used == 0 )
691 {
692 if( val == 0 )
693 return false;
694
695 return (val < 0);
696 }
697
698 if( negative != (val < 0) )
699 return !negative;
700
701 if( used > 1 )
702 return true;
703
704 if( val < 0 )
705 tmp = uint32( (-int64(val))+int64(1) );
706 else
707 tmp = uint32(val);
708
709 if( negative )
710 return ( data[0] < tmp );
711 return ( data[0] > tmp );
712 }
713
operator -(const Integer & val)714 Integer operator-(const Integer &val) throw(error_obj)
715 {
716 Integer tmp;
717
718 tmp = val;
719 tmp.negative = !tmp.negative;
720
721 return tmp;
722 }
723
enlarge_to(uint32 new_size)724 void Integer::enlarge_to(uint32 new_size) throw(error_obj)
725 {
726 if( size < new_size )
727 {
728 if( new_size > 2 )
729 {
730 uint32 *new_data;
731 bool use_delete = ( size > 2 );
732
733 try{ new_data = new uint32[new_size]; }
734 catch(...) { THROW_ERROR( ErrorType_Memory, _("Couldn't get memory.") ); }
735
736 size = new_size;
737
738 for( uint32 i=0; i<used; i++ )
739 new_data[i] = data[i];
740
741 if( use_delete )
742 delete [] data;
743 data = new_data;
744 }
745 else
746 {
747 size = new_size;
748 data = buf;
749 }
750 }
751 }
752
operator ++(void)753 Integer & Integer::operator++(void) throw(error_obj)
754 {
755 if( used == 0 )
756 {
757 enlarge_to( 1 );
758 data[0] = 1;
759 used = 1;
760 negative = false;
761 return *this;
762 }
763
764 if( negative )
765 {
766 for( uint32 i=0; ; i++ )
767 {
768 data[i]--;
769 if( data[i] != uint32_max )
770 break;
771 }
772 if( data[used-1] == 0 )
773 used--;
774 }
775 else
776 {
777 if( data[used-1] == uint32_max )
778 enlarge_to( used+1 );
779
780 for( uint32 i=0; ; i++ )
781 {
782 if( i == used )
783 {
784 data[i] = 1;
785 used++;
786 break;
787 }
788 data[i]++;
789 if( data[i] != 0 )
790 break;
791 }
792 }
793
794 return *this;
795 }
796
operator --(void)797 Integer & Integer::operator--(void) throw(error_obj)
798 {
799 if( used == 0 )
800 {
801 enlarge_to( 1 );
802 data[0] = 1;
803 used = 1;
804 negative = true;
805 return *this;
806 }
807 else if( data[used-1] == uint32_max )
808 enlarge_to( used+1 );
809
810 if( !negative )
811 {
812 for( uint32 i=0; ; i++ )
813 {
814 data[i]--;
815 if( data[i] != uint32_max )
816 break;
817 }
818 if( data[used-1] == 0 )
819 used--;
820 }
821 else
822 {
823 for( uint32 i=0; ; i++ )
824 {
825 if( i == used )
826 {
827 data[i] = 1;
828 used = i+1;
829 break;
830 }
831 data[i]++;
832 if( data[i] != 0 )
833 break;
834 }
835 }
836
837 return *this;
838 }
839
add_data(const Integer & nr)840 void Integer::add_data( const Integer &nr ) throw(error_obj)
841 {
842 uint32 i;
843
844 if( nr.used == 0 ) // nothing to add
845 return;
846
847 if( nr.used >= size )
848 {
849 enlarge_to( nr.used + 1 );
850 for( i=used; i<(nr.used+1); i++ )
851 data[i] = 0;
852 }
853 else if( size == used )
854 {
855 enlarge_to( size + 1 );
856 data[used] = 0;
857 used++;
858 }
859
860 if( used <= nr.used )
861 {
862 for( i=used; i<=nr.used; i++ )
863 data[i] = 0;
864 used = nr.used + 1;
865 }
866
867 {
868 uint32 overflow=0, low_used, *ptr, *ptr2;
869
870 ptr = data;
871 ptr2 = nr.data;
872 low_used = ( used < nr.used ) ? used : nr.used;
873 for( i=0; i<low_used; i++, ptr++, ptr2++ )
874 {
875 if( (*ptr += *ptr2 + overflow) <= *ptr2 )
876 {
877 if( *ptr < *ptr2 )
878 overflow = 1;
879 //else // *ptr == *ptr2
880 // overflow = overflow;
881 }
882 else
883 overflow = 0;
884 }
885 if( overflow )
886 {
887 i--;
888 do
889 {
890 i++;
891 data[i]++;
892 }while( data[i] == 0 );
893 }
894 }
895
896 if( used != 0 )
897 if( data[used-1] == 0 )
898 used--;
899 }
900
add_data_uint32_shifted(const Integer & nr,uint32 shift)901 void Integer::add_data_uint32_shifted( const Integer &nr, uint32 shift) throw(error_obj)
902 {
903 uint32 i;
904
905 if( nr.used == 0 ) // nothing to add
906 return;
907
908 if( (nr.used+shift) >= size )
909 {
910 enlarge_to( nr.used + shift + 1 );
911 for( i=used; i<(nr.used+shift+1); i++ )
912 data[i] = 0;
913 }
914 else if( size == used )
915 {
916 enlarge_to( size + 1 );
917 data[used] = 0;
918 used++;
919 }
920
921 if( used <= (nr.used+shift) )
922 {
923 for( i=used; i<=(nr.used+shift); i++ )
924 data[i] = 0;
925 used = nr.used + shift + 1;
926 }
927
928 {
929 uint32 overflow=0, low_used, *ptr, *ptr2;
930
931 ptr = &data[shift];
932 ptr2 = nr.data;
933 low_used = ( used < nr.used ) ? used : nr.used;
934 for( i=0; i<low_used; i++, ptr++, ptr2++ )
935 {
936 if( (*ptr += *ptr2 + overflow) <= *ptr2 )
937 {
938 if( *ptr < *ptr2 )
939 overflow = 1;
940 //else // *ptr == *ptr2
941 // overflow = overflow;
942 }
943 else
944 overflow = 0;
945 }
946 if( overflow )
947 {
948 do
949 {
950 (*ptr)++;
951 }while( *ptr++ == 0 );
952 }
953 }
954
955 if( used != 0 )
956 if( data[used-1] == 0 )
957 used--;
958 }
959
sub_data_reverse(const Integer & nr)960 void Integer::sub_data_reverse( const Integer &nr )
961 {
962 Integer res;
963 res = nr;
964 res.sub_data( *this );
965 *this = res;
966 }
967
968 //
969 // this must be larger than nr....no checking for that will be done
970 //
sub_data(const Integer & nr)971 void Integer::sub_data( const Integer &nr )
972 {
973 uint32 i;
974
975 {
976 uint64 tmp, mask, borrowed=0;
977 uint32 *ptr, *ptr2;
978 mask = uint64( uint32_max );
979
980 ptr = data;
981 ptr2 = nr.data;
982 for( i=0; i<nr.used; i++, ptr++, ptr2++ )
983 {
984 tmp = uint64(*ptr) - uint64(*ptr2) - borrowed;
985 if( tmp > mask )
986 {
987 borrowed = 1;
988 tmp &= mask;
989 }
990 else
991 borrowed = 0;
992
993 *ptr = uint32(tmp);
994 }
995 if( borrowed )
996 {
997 for( ; ; i++ )
998 {
999 data[i]--;
1000 if( data[i] != uint32_max )
1001 break;
1002 }
1003 }
1004 }
1005
1006 for( i=used-1; i != uint32_max; i-- )
1007 {
1008 if( data[i] != 0 )
1009 break;
1010 }
1011 used = i+1;
1012 }
1013
operator +(const Integer & val) const1014 Integer Integer::operator+(const Integer &val) const throw(error_obj)
1015 {
1016 Integer res;
1017
1018 if( negative == val.negative )
1019 {
1020 res = *this;
1021 res.add_data( val );
1022 res.negative = negative;
1023 }
1024 else
1025 {
1026 if( val.negative )
1027 {
1028 if( compare_abs_value( val ) >= 0 )
1029 {
1030 res = *this;
1031 res.sub_data( val );
1032 res.negative = false;
1033 }
1034 else
1035 {
1036 res = val;
1037 res.sub_data( *this );
1038 res.negative = true;
1039 }
1040 }
1041 else
1042 {
1043 if( compare_abs_value( val ) > 0 )
1044 {
1045 res = *this;
1046 res.sub_data( val );
1047 res.negative = true;
1048 }
1049 else
1050 {
1051 res = val;
1052 res.sub_data( *this );
1053 res.negative = false;
1054 }
1055 }
1056 }
1057 return res;
1058 }
1059
operator -(const Integer & val) const1060 Integer Integer::operator-(const Integer &val) const throw(error_obj)
1061 {
1062 Integer res;
1063
1064 if( negative != val.negative )
1065 {
1066 res = *this;
1067 res.add_data( val );
1068 res.negative = negative;
1069 }
1070 else
1071 {
1072 if( !negative )
1073 {
1074 if( compare_abs_value( val ) >= 0 )
1075 {
1076 res = *this;
1077 res.sub_data( val );
1078 res.negative = false;
1079 }
1080 else
1081 {
1082 res = val;
1083 res.sub_data( *this );
1084 res.negative = true;
1085 }
1086 }
1087 else
1088 {
1089 if( compare_abs_value( val ) > 0 )
1090 {
1091 res = *this;
1092 res.sub_data( val );
1093 res.negative = true;
1094 }
1095 else
1096 {
1097 res = val;
1098 res.sub_data( *this );
1099 res.negative = false;
1100 }
1101 }
1102 }
1103 return res;
1104 }
1105
mul_by_2(void)1106 void Integer::mul_by_2(void) throw(error_obj)
1107 {
1108 if( used == 0 )
1109 return;
1110
1111 if( data[used-1] & (uint32(1)<<31) )
1112 {
1113 enlarge_to( used + 1 );
1114 data[used] = 0;
1115 used++;
1116 }
1117
1118 for( uint32 i=used-1; i>0; i-- )
1119 {
1120 data[i] <<= 1;
1121 if( data[i-1] & (uint32(1)<<31) )
1122 data[i]++;
1123 }
1124 data[0] <<= 1;
1125 }
1126
mul_by_2_pow_32(uint32 n)1127 void Integer::mul_by_2_pow_32(uint32 n) throw(error_obj)
1128 {
1129 if( used == 0 || n == 0 )
1130 return;
1131
1132 if( size < (used+n) )
1133 {
1134 uint32 *new_data;
1135 bool use_delete = ( size > 2 );
1136
1137 try{ new_data = new uint32[used+n+1]; }
1138 catch(...) { THROW_ERROR( ErrorType_Memory, _("Couldn't get memory.") ); }
1139
1140 size = used+n+1;
1141
1142 for( uint32 i=used+n-1; i>(n-1); i-- )
1143 new_data[i] = data[i-n];
1144
1145 for( uint32 i=0; i<n; i++ )
1146 new_data[i] = 0;
1147
1148 used += n;
1149 if( use_delete )
1150 delete [] data;
1151 data = new_data;
1152 }
1153 else
1154 {
1155 for( uint32 i=used+n-1; i>(n-1); i-- )
1156 data[i] = data[i-n];
1157
1158 for( uint32 i=0; i<n; i++ )
1159 data[i] = 0;
1160 used += n;
1161 }
1162 }
1163
div_by_2(void)1164 void Integer::div_by_2(void) throw(error_obj)
1165 {
1166 if( used == 0 )
1167 return;
1168
1169 data[0] >>= 1;
1170 for( uint32 i=1; i<used; i++ )
1171 {
1172 data[i-1] += ( (data[i] & uint32(1)) << 31);
1173 data[i] >>= 1;
1174 }
1175
1176 if( data[used-1] == 0 )
1177 used--;
1178 }
1179
div_by_2_pow_32(void)1180 void Integer::div_by_2_pow_32(void) throw(error_obj)
1181 {
1182 if( used == 0 )
1183 return;
1184
1185 used--;
1186 for( uint32 i=0; i<used; i++ )
1187 data[i] = data[i+1];
1188 }
1189
1190 // special function, used by divide *this -= nr * 2^(32*shift) * mult
1191 // this must be larger than nr * 2^(32*shift) * mult
sub_uint32_mult_shifted(uint32 mult,const Integer & nr,uint32 shift)1192 void Integer::sub_uint32_mult_shifted( uint32 mult, const Integer &nr, uint32 shift )
1193 {
1194 uint64 tmp, mult64, mask, borrowed=0, tmp_hi;
1195 uint32 i, *ptr=&data[shift], *ptr2=nr.data;
1196
1197 mult64 = uint64(mult);
1198 mask = uint64( uint32_max );
1199
1200 for( i=nr.used; i; i-- )
1201 {
1202 tmp = mult64 * uint64(*ptr2++);
1203 if( tmp > mask )
1204 {
1205 tmp_hi = tmp >> 32;
1206 tmp &= mask;
1207 }
1208 else
1209 tmp_hi = 0;
1210
1211 tmp = uint64(*ptr) - tmp - borrowed;
1212 if( tmp > mask )
1213 {
1214 borrowed = 1;
1215 tmp &= mask;
1216 }
1217 else
1218 borrowed = 0;
1219
1220 *ptr++ = uint32(tmp);
1221
1222 if( tmp_hi )
1223 {
1224 tmp = uint64(*ptr) - tmp_hi;
1225 if( tmp > mask )
1226 {
1227 *ptr = uint32(tmp & mask);
1228 for( uint32 *ptr3=ptr+1; ; )
1229 {
1230 (*ptr3)--;
1231 if( *ptr3++ != uint32_max )
1232 break;
1233 }
1234 }
1235 else
1236 *ptr = uint32(tmp);
1237 }
1238 }
1239 if( borrowed )
1240 {
1241 for(;;)
1242 {
1243 (*ptr)--;
1244 if( *ptr++ != uint32_max )
1245 break;
1246 }
1247 }
1248 while( used != 0 )
1249 {
1250 if( data[used-1] == 0 )
1251 used--;
1252 else
1253 break;
1254 }
1255 }
1256
1257 // special function, used by divide *this += nr * 2^(32*shift)
1258 // this must be large enough and the data should be zero filled
add_uint32_shifted(uint32 nr,uint32 shift)1259 void Integer::add_uint32_shifted( uint32 nr, uint32 shift ) throw(error_obj)
1260 {
1261 data[shift] += nr;
1262 if( data[shift] < nr ) // overflowed
1263 {
1264 do{
1265 shift++;
1266 data[shift]++;
1267 }while( data[shift] == 0 );
1268 }
1269 }
1270
divide(const Integer & divider,Integer * ans,Integer * rest) const1271 void Integer::divide( const Integer ÷r, Integer *ans, Integer *rest ) const throw(error_obj)
1272 {
1273 if( divider.used == 0 )
1274 THROW_ERROR( ErrorType_Divide_by_zero, _("Divide by zero") );
1275
1276 if( ans == 0 && rest == 0 )
1277 return;
1278
1279 if( ans )
1280 *ans = 0;
1281
1282 if( this->compare_abs_value( divider ) < 0 )
1283 {
1284 if( rest )
1285 *rest = *this;
1286 return;
1287 }
1288
1289 if( ans )
1290 {
1291 ans->enlarge_to( used - divider.used + 1 );
1292
1293 for( uint32 i=0; i<ans->size; i++ )
1294 ans->data[i] = 0;
1295 }
1296
1297 if( used <= 2 && divider.used <= 2 )
1298 {
1299 uint64 tmp_nr, tmp_div, res;
1300
1301 tmp_nr = uint64( data[0] );
1302 if( used == 2 )
1303 tmp_nr += uint64( data[1] ) << 32;
1304
1305 tmp_div = uint64( divider.data[0] );
1306 if( divider.used == 2 )
1307 tmp_div += uint64( divider.data[1] ) << 32;
1308
1309 res = tmp_nr / tmp_div;
1310
1311 if( ans )
1312 {
1313 ans->data[0] = uint32( res & uint64(uint32_max) );
1314 if( res > uint64(uint32_max) )
1315 {
1316 ans->data[1] = uint32( res >> 32 );
1317 ans->used = 2;
1318 }
1319 else
1320 ans->used = 1;
1321 ans->negative = negative ^ divider.negative;
1322 }
1323
1324 if( rest )
1325 {
1326 rest->enlarge_to( 2 );
1327
1328 tmp_nr -= res*tmp_div;
1329 rest->data[0] = uint32( tmp_nr & uint64(uint32_max) );
1330 if( tmp_nr > uint64(uint32_max) )
1331 {
1332 rest->data[1] = uint32( tmp_nr >> 32 );
1333 rest->used = 2;
1334 }
1335 else
1336 rest->used = ( rest->data[0] != 0 );
1337 rest->negative = negative;
1338 }
1339 }
1340 else
1341 {
1342 Integer tnr( *this ), tdiv( divider );
1343 uint32 appr_mult, tdiv_shift;
1344 uint64 div;
1345
1346 if( ans )
1347 {
1348 ans->enlarge_to( tnr.used - tdiv.used +1 );
1349 ans->used = tnr.used - tdiv.used +1;
1350 for( uint32 i=0; i<ans->used; i++ )
1351 ans->data[i] = 0;
1352 }
1353
1354 div = uint64(tdiv.data[tdiv.used-1]);
1355 div++;
1356
1357 tdiv_shift = tnr.used - tdiv.used;
1358 while( tnr.compare_abs_value( tdiv ) >= 0 )
1359 {
1360 while( tnr.compare_abs_value_shifted( tdiv, tdiv_shift ) < 0 )
1361 tdiv_shift--;
1362
1363 if( tnr.used > (tdiv.used + tdiv_shift) )
1364 appr_mult = uint32( ( (uint64(tnr.data[tnr.used-1])<<32) + uint64(tnr.data[tnr.used-2]) ) / div );
1365 else
1366 appr_mult = uint32( uint64(tnr.data[tnr.used-1]) / div );
1367
1368 if( appr_mult == 0 )
1369 appr_mult = 1;
1370
1371 // tnr -= tdiv * 2^(32*tdiv_shift) * appr_mult;
1372 tnr.sub_uint32_mult_shifted( appr_mult, tdiv, tdiv_shift );
1373
1374 if( ans ) // *ans += appr_mult * 2^(32*tdiv_shift)
1375 ans->add_uint32_shifted( appr_mult, tdiv_shift );
1376 }
1377
1378 if( ans )
1379 {
1380 while( ans->used != 0 )
1381 {
1382 if( ans->data[ans->used-1] == 0 )
1383 ans->used--;
1384 else
1385 break;
1386 }
1387 }
1388
1389 if( ans )
1390 ans->negative = negative ^ divider.negative;
1391
1392 if( rest )
1393 {
1394 rest->swap( tnr );
1395 rest->negative = negative;
1396 }
1397 }
1398 }
1399
add(const Integer & val)1400 void Integer::add(const Integer &val) throw(error_obj)
1401 {
1402 if( negative == val.negative )
1403 add_data( val );
1404 else
1405 {
1406 if( val.negative )
1407 {
1408 if( compare_abs_value( val ) >= 0 )
1409 {
1410 sub_data( val );
1411 negative = false;
1412 }
1413 else
1414 {
1415 sub_data_reverse( val );
1416 negative = true;
1417 }
1418 }
1419 else
1420 {
1421 if( compare_abs_value( val ) > 0 )
1422 {
1423 sub_data( val );
1424 negative = true;
1425 }
1426 else
1427 {
1428 sub_data_reverse( val );
1429 negative = false;
1430 }
1431 }
1432 }
1433 }
1434
sub(const Integer & val)1435 void Integer::sub(const Integer &val) throw(error_obj)
1436 {
1437 if( negative != val.negative )
1438 add_data( val );
1439 else
1440 {
1441 if( !negative )
1442 {
1443 if( compare_abs_value( val ) >= 0 )
1444 {
1445 sub_data( val );
1446 negative = false;
1447 }
1448 else
1449 {
1450 sub_data_reverse( val );
1451 negative = true;
1452 }
1453 }
1454 else
1455 {
1456 if( compare_abs_value( val ) > 0 )
1457 {
1458 sub_data( val );
1459 negative = true;
1460 }
1461 else
1462 {
1463 sub_data_reverse( val );
1464 negative = false;
1465 }
1466 }
1467 }
1468 }
1469
count_used_bits(void) const1470 uint32 Integer::count_used_bits(void) const
1471 {
1472 uint32 tmp, i;
1473
1474 if( used == 0 )
1475 return 0;
1476
1477 tmp = data[used-1];
1478 for( i=0; tmp; i++ )
1479 tmp >>= 1;
1480
1481 return (used-1)*32 + i;
1482 }
1483
set_bit(uint32 bit)1484 void Integer::set_bit( uint32 bit ) throw(error_obj)
1485 {
1486 enlarge_to( bit/32 +1 );
1487
1488 if( (bit/32 +1) > used )
1489 {
1490 for( uint32 i=used; i<(bit/32 +1); i++ )
1491 data[i] = 0;
1492
1493 used = bit/32 +1;
1494 }
1495
1496 data[bit/32] |= uint32(1) << (bit%32);
1497 }
1498
clear_bit(uint32 bit)1499 void Integer::clear_bit( uint32 bit ) throw(error_obj)
1500 {
1501 if( (bit/32 +1) > used )
1502 return;
1503
1504 data[bit/32] &= ~(uint32(1) << (bit%32));
1505 if( used == (bit/32 +1) )
1506 {
1507 for( ; used != 0 && data[used-1] == 0; used-- )
1508 ;
1509 }
1510 }
1511
check_bit(uint32 bit) const1512 bool Integer::check_bit( uint32 bit ) const throw(error_obj)
1513 {
1514 if( (bit/32 +1) > used )
1515 return false;
1516
1517 if( data[bit/32] & (uint32(1) << (bit%32)) )
1518 return true;
1519 return false;
1520 }
1521
iSqrt(const Integer & var)1522 Integer iSqrt( const Integer &var ) throw(error_obj)
1523 {
1524 Integer x, tmp;
1525
1526 if( var.negative )
1527 THROW_ERROR( ErrorType_Domain, _("Domain error: Number must be positive in iSqrt.") );
1528
1529 if( var.used == 0 )
1530 {
1531 x.used = 0;
1532 return x;
1533 }
1534
1535 x.enlarge_to( (var.used+1)/2 ); // makes room for the start guess
1536 {
1537 uint32 ans_bits = (var.count_used_bits()+1)/2;
1538 x.set_bit( ans_bits-1 ); // make the start guess
1539 if( ans_bits >= 3 )
1540 {
1541 x.set_bit( ans_bits-3 );
1542 if( !(var.count_used_bits() & 1) )
1543 x.set_bit( ans_bits-2 );
1544 }
1545 }
1546
1547 do
1548 {
1549 // nexton-raphson's method for solving sqrt p = x
1550 var.divide( x, &tmp, 0 ); // X[n+1] = ( X[n] + p/X[n] ) / 2
1551 x.add( tmp );
1552 x.div_by_2();
1553
1554 x.mul( x, &tmp ); // this code checks to see if the loop is finished
1555 tmp.add( x ); // n^2 + 2n = (n+1)^2 -1
1556 tmp.add( x ); // tmp2 = x^2 + 2x
1557 }while( tmp.compare_abs_value( var ) < 0 );
1558
1559 return x;
1560 }
1561
power(Integer nr,Integer * dest) const1562 void Integer::power( Integer nr, Integer *dest ) const throw(error_obj)
1563 {
1564 Integer tmp;
1565 uint32 power;
1566
1567 if( dest == 0 )
1568 return;
1569
1570 if( used == 0 )
1571 {
1572 if( nr.used == 0 )
1573 {
1574 *dest = 1;
1575 return;
1576 }
1577 else
1578 {
1579 dest->used = 0;
1580 return;
1581 }
1582 }
1583
1584 if( nr.used > 1 )
1585 {
1586 if( used == 1 && data[0] == 1 )
1587 {
1588 dest->enlarge_to( 1 );
1589 dest->used = 1;
1590 dest->negative = false;
1591 dest->data[0] = 1;
1592 return;
1593 }
1594 else
1595 THROW_ERROR( ErrorType_Overflow, _("Overflow") );
1596 }
1597
1598 if( nr.used == 0 )
1599 {
1600 dest->enlarge_to( 1 );
1601 dest->used = 1;
1602 dest->negative = false;
1603 dest->data[0] = 1;
1604 return;
1605 }
1606
1607 power = nr.data[0];
1608 nr = *this;
1609
1610 if( power & 1 )
1611 *dest = *this;
1612 else
1613 *dest = 1;
1614
1615 while( power >>= 1 )
1616 {
1617 nr.mul( nr, &tmp );
1618 nr = tmp;
1619
1620 if( power & 1 )
1621 {
1622 dest->mul( nr, &tmp );
1623 *dest = tmp;
1624 }
1625 }
1626 }
1627
mul_data(const Integer & factor,Integer * dest) const1628 void Integer::mul_data( const Integer &factor, Integer *dest ) const throw(error_obj)
1629 {
1630 uint32 i, i2, *ptr, *ptr_dest;
1631 const uint32 *ptr2;
1632 uint64 overflow=0, tmp;
1633
1634 if( dest == 0 )
1635 return;
1636
1637 dest->enlarge_to( used + factor.used );
1638 dest->used = dest->size;
1639
1640 for( i=0; i<dest->used; i++ )
1641 dest->data[i] = 0;
1642
1643 ptr = data;
1644 for( i=0; i<used; i++, ptr++ )
1645 {
1646 tmp = *ptr;
1647 ptr2 = factor.data;
1648 ptr_dest = &(dest->data[i]);
1649 for( i2=0; i2<factor.used; i2++ )
1650 {
1651 overflow += uint64(*ptr_dest) + tmp * uint64(*ptr2++);
1652 *ptr_dest++ = uint32( overflow );
1653 overflow >>= 32;
1654 }
1655 do{
1656 overflow += uint64(*ptr_dest);
1657 *ptr_dest++ = uint32( overflow );
1658 overflow >>= 32;
1659 }while( overflow );
1660 }
1661
1662 for( i=dest->used-1; i != uint32_max; i-- )
1663 {
1664 if( dest->data[i] != 0 )
1665 break;
1666 }
1667 dest->used = i+1;
1668 }
1669
mul(const Integer & factor,Integer * dest) const1670 void Integer::mul( const Integer &factor, Integer *dest ) const throw(error_obj)
1671 {
1672 if( dest == 0 )
1673 return;
1674
1675 if( used < 100 || factor.used < 100 ) // this limit is probobly not the best for all cpus but it's
1676 mul_data( factor, dest ); // likely to be good enough
1677 else
1678 { // here is a Recursive Divide & Conquer multiply implementation
1679 Integer ah, al, bh, bl, X;
1680 uint32 base;
1681
1682 base = ( (used>=factor.used) ? used : factor.used ) /2;
1683
1684 dest->enlarge_to( used + factor.used );
1685
1686 extract( &ah, base, used-1 );
1687 extract( &al, 0, base-1 );
1688 factor.extract( &bh, base, factor.used-1 );
1689 factor.extract( &bl, 0, base-1 );
1690
1691 al.mul( bl, dest ); // dest = al*bl
1692 ah.mul( bh, &X ); // X = ah*bh
1693 bh.add_data( bl ); // bh += bl
1694 ah.add_data( al ); // ah += al
1695 ah.mul( bh, &al ); // al = ah*bh = (ah+al)*(bh+bl)
1696 al.sub_data( X ); // al -= X
1697 al.sub_data( *dest ); // al -= dest
1698
1699 dest->add_data_uint32_shifted( al, base );
1700 dest->add_data_uint32_shifted( X, base*2 );
1701 }
1702 dest->negative = negative ^ factor.negative;
1703 }
1704
faculty(void)1705 void Integer::faculty(void) throw(error_obj)
1706 {
1707 if( used >= 2 )
1708 THROW_ERROR( ErrorType_Overflow, _("Overflow") );
1709
1710 if( negative )
1711 THROW_ERROR( ErrorType_Domain, _("Domain error: Can't calculate faculty of a negative number.") );
1712
1713 if( used == 0 )
1714 {
1715 enlarge_to( 1 );
1716 data[0] = 1;
1717 used = 1;
1718 return;
1719 }
1720
1721 Integer tmp, tmp2, tmp3(1);
1722 uint32 twos = 0, this_many, take_many = 1, taken_this = 0;
1723 static const uint32 limit[] = { 0, 92681, 2048, 430, 128, 64, 35, 29, 1 };
1724
1725 tmp = *this;
1726 while( *tmp.data <= limit[take_many] )
1727 take_many++;
1728
1729 // this loop calculates the faculty without all 2 factors, they are fixed after the loop
1730 // it also takes upto to five factors at a time (as long as their product is less than 2^32-1
1731 // because that multiplication is done in O(1) instead of O(n) as is the case when
1732 // multipling it with the total product
1733 for( (*tmp.data)--; *tmp.data > uint32(1); (*tmp.data)-- )
1734 {
1735 this_many = 0;
1736 while( !(*tmp.data & 1) )
1737 {
1738 this_many++;
1739 *tmp.data >>= 1;
1740 }
1741 *tmp3.data *= *tmp.data;
1742 taken_this++;
1743 twos += this_many;
1744 *tmp.data <<= this_many;
1745 if( taken_this == take_many )
1746 {
1747 this->mul( tmp3, &tmp2 );
1748 *this = tmp2;
1749
1750 taken_this = 0;
1751 *tmp3.data = 1;
1752 if( *tmp.data <= limit[take_many] )
1753 take_many++;
1754 }
1755 }
1756 if( *tmp3.data != 1 )
1757 {
1758 this->mul( tmp3, &tmp2 );
1759 *this = tmp2;
1760 }
1761 this->mul_by_2_pow_32( twos/32 );
1762 twos %= 32;
1763 while( twos-- != 0 )
1764 this->mul_by_2();
1765 }
1766
perm(Integer n,Integer k)1767 void Integer::perm( Integer n, Integer k ) throw(error_obj)
1768 {
1769 if( n.negative || k.negative )
1770 THROW_ERROR( ErrorType_Domain, _("Domain error: Can't calculate perm(n,k) if n or k is negative.") );
1771
1772 if( n.compare_abs_value( k ) < 0 )
1773 THROW_ERROR( ErrorType_Domain, _("Domain error: Can't calculate perm(n,k) when k > n.") );
1774
1775 Integer tmp;
1776 tmp = n;
1777 tmp.sub( k );
1778 k = tmp;
1779
1780 *this = 1;
1781
1782 for( ; n>k; n-- )
1783 {
1784 this->mul( n, &tmp );
1785 *this = tmp;
1786 }
1787 }
1788
comb(const Integer & n,Integer k)1789 void Integer::comb( const Integer &n, Integer k ) throw(error_obj)
1790 {
1791 if( n.negative || k.negative )
1792 THROW_ERROR( ErrorType_Domain, _("Domain error: Can't calculate comb(n,k) if n or k is negative.") );
1793
1794 if( n.compare_abs_value( k ) < 0 )
1795 THROW_ERROR( ErrorType_Domain, _("Domain error: Can't calculate comb(n,k) when k > n.") );
1796
1797 Integer tmp;
1798
1799 tmp = n;
1800 tmp.sub( k );
1801 if( tmp < k )
1802 k = tmp;
1803
1804 tmp.perm( n, k );
1805 k.faculty();
1806
1807 tmp.divide( k, this, 0 );
1808 }
1809
extract(Integer * dest,uint32 start,uint32 stop) const1810 void Integer::extract( Integer *dest, uint32 start, uint32 stop ) const throw(error_obj)
1811 {
1812 if( dest == 0 )
1813 return;
1814
1815 if( used == 0 )
1816 {
1817 *dest = 0;
1818 return;
1819 }
1820 if( stop >= used )
1821 stop = used -1;
1822
1823 if( start > stop )
1824 {
1825 *dest = 0;
1826 return;
1827 }
1828
1829 dest->enlarge_to( stop-start+1 );
1830 dest->used = stop-start+1;
1831
1832 for( uint32 i=0; start <= stop; i++, start++ )
1833 dest->data[i] = data[start];
1834
1835 if( dest->data[dest->used-1] == 0 )
1836 {
1837 for( ; dest->used != 0 && dest->data[dest->used-1] == 0 ; dest->used-- )
1838 ;
1839 }
1840 }
1841
1842 // Calculates dest = [ (n^p) mod m ]
powMod(Integer * dest,Integer n,Integer p,const Integer & m)1843 void powMod( Integer *dest, Integer n, Integer p, const Integer &m ) throw(error_obj)
1844 {
1845 Integer tmp;
1846
1847 if( dest == 0 )
1848 return;
1849
1850 if( p.isNegative() )
1851 THROW_ERROR( ErrorType_Domain, _("Domain error: result not an integer when raising to negative numbers!") );
1852
1853 if( m.isNegative() || m.isZero() )
1854 THROW_ERROR( ErrorType_Domain, _("Domain error: powMod: m must be a positive integer!") );
1855
1856 if( p.isZero() )
1857 {
1858 Integer(1).divide( m, 0, dest );
1859 return;
1860 }
1861
1862 if( n.isZero() )
1863 {
1864 dest = 0;
1865 return;
1866 }
1867
1868 if( n.get_used() == 1 && n.get_data()[0] == 1 )
1869 {
1870 Integer(1).divide( m, 0, dest );
1871 return;
1872 }
1873
1874 n.divide( m, 0, dest );
1875 n = *dest;
1876 if( !(p.get_data()[0] & 1) )
1877 *dest = 1;
1878
1879 p.div_by_2();
1880 while( !p.isZero() )
1881 {
1882 n.mul( n, &tmp );
1883 tmp.divide( m, 0, &n );
1884
1885 if( p.get_data()[0] & 1 )
1886 {
1887 dest->mul( n, &tmp );
1888 tmp.divide( m, 0, dest );
1889 }
1890 p.div_by_2();
1891 }
1892 }
1893