Thread: Bignum math: division

  1. #1
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    657

    Bignum math: division

    I got as far as this:
    Code:
    int div__mcc_int( mcc_int_t *num, mcc_int_t const * const val, mcc_int_t *rem ) {
    	int ret = mcc_int_validate2( num, val );
    	mcc_int_t seg = {0};
    	mcc_int_seg_t bits = 0;
    	if ( ret != EXIT_SUCCESS ) return ret;
    	ret = mcc_int_validate(rem);
    	if ( ret != EXIT_SUCCESS )
    		return (ret == EADDRNOTAVAIL) ? EDESTADDRREQ : ret;
    	if ( rem->size != num->size ) return ERANGE;
    	seg = *rem;
    	seg.zero = seg.stop;
    	(void)memcpy( rem->zero.seg, num->zero.seg, num->size );
    	(void)memset( num->zero.seg, 0, num->size );
    	if ( eql__mcc_int( val, NULL ) ) return EXIT_SUCCESS;
    	// The ' && seg.zero.b' here is to prevent a somehow infinite loop
    	while ( gte__mcc_int( rem, val ) && seg.zero.b ) {
    		seg.zero = dec_mcc_bit(seg.zero);
    		if ( gte__mcc_int( &seg, val ) ) {
    			shl___mcc_int( num, bits );
    			sub__mcc_int( &seg, val );
    			*(num->zero.seg) |= num->zero.bit;
    			bits = 0;
    		}
    		++bits;
    	}
    	if ( bits ) shl___mcc_int( num, bits );
    	return EXIT_SUCCESS;
    }
    GDB online Debugger | Code, Compile, Run, Debug online C, C++
    Which gives me this:
    Code:
    gcc -Wall -o "bimath" "bimath.c" && "./bimath"
    _num = 0000000000000000, num = 0000000000000000, _rem = 0000000000000040, rem = 0000000000000040 op = '=='
    _num = 0000000000000001, num = 0000000000000001, _rem = 0000000000000040, rem = 0000000000000040 op = '!='
    _num = 0000000000000001, num = 0000000000000001, _rem = 0000000000000040, rem = 0000000000000040 op = '>'
    _num = 0000000000000001, num = 0000000000000001, _rem = 0000000000000040, rem = 0000000000000040 op = '>='
    _num = 0000000000000000, num = 0000000000000000, _rem = 0000000000000040, rem = 0000000000000040 op = '<'
    _num = 0000000000000000, num = 0000000000000000, _rem = 0000000000000040, rem = 0000000000000040 op = '<='
    _num = 0000000000000100, num = 0000000000000100, _rem = 0000000000000040, rem = 0000000000000040 op = '<<'
    _num = 0000000000000010, num = 0000000000000010, _rem = 0000000000000040, rem = 0000000000000040 op = '>>'
    _num = 0000000000000042, num = 0000000000000042, _rem = 0000000000000040, rem = 0000000000000040 op = '|'
    _num = 0000000000000000, num = 0000000000000000, _rem = 0000000000000040, rem = 0000000000000040 op = '&'
    _num = 0000000000000042, num = 0000000000000042, _rem = 0000000000000040, rem = 0000000000000040 op = '^'
    _num = 0000000000000042, num = 0000000000000042, _rem = 0000000000000040, rem = 0000000000000040 op = '+'
    _num = 0000000000000080, num = 0000000000000080, _rem = 0000000000000040, rem = 0000000000000040 op = '*'
    _num = 000000000000003E, num = 000000000000003E, _rem = 0000000000000040, rem = 0000000000000040 op = '-'
    _num = 0000000000000001, num = 000000000000003E, _rem = 0000000000000042, rem = 0000000000000000 op = '/'
    Compilation finished successfully.
    Now obviously the last result is incorrect, any ideas as to what is causing it cause I'm fresh outa ideas (this is btw the problem I always run into whenever I try to do binary division)

  2. #2
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    657
    Never mind, I finally got it:
    Code:
    int div__mcc_int( mcc_int_t *num, mcc_int_t const * const val, mcc_int_t *rem ) {
    	int ret = mcc_int_validate2( num, val );
    	mcc_int_t seg = {0};
    	mcc_int_seg_t bits = 0;
    	if ( ret != EXIT_SUCCESS ) return ret;
    	ret = mcc_int_validate(rem);
    	if ( ret != EXIT_SUCCESS )
    		return (ret == EADDRNOTAVAIL) ? EDESTADDRREQ : ret;
    	if ( rem->size != num->size ) return ERANGE;
    	(void)memcpy( rem->zero.seg, num->zero.seg, num->size );
    	(void)memset( num->zero.seg, 0, num->size );
    	if ( eql__mcc_int( val, NULL ) ) return EXIT_SUCCESS;
    	seg = *rem;
    	while ( seg.stop.b ) {
    		seg.stop = dec_mcc_bit(seg.stop);
    		if ( *(seg.stop.seg) & seg.stop.bit ) {
    			seg.stop = inc_mcc_bit(seg.stop);
    			break;
    		}
    	}
    	seg.zero = seg.stop;
    	seg.zero = dec_mcc_bit(seg.zero);
    	while ( seg.zero.b ) {
    		if ( gte__mcc_int( &seg, val ) ) {
    			shl___mcc_int( num, bits );
    			sub__mcc_int( &seg, val );
    			*(num->zero.seg) |= num->zero.bit;
    			bits = 0;
    		}
    		++bits;
    		seg.zero = dec_mcc_bit(seg.zero);
    	}
    	if ( bits ) shl___mcc_int( num, bits );
    	return EXIT_SUCCESS;
    }
    I can now finally convert my FPN function and see if it was just not enough space in the integer. BTW anyone planning on using the functions for themselves should note that I forgot to clear num in mul__mcc_int() before the loop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bignum math: right shift
    By awsdert in forum C Programming
    Replies: 1
    Last Post: 2 Weeks Ago, 05:13 AM
  2. Replies: 2
    Last Post: 06-07-2011, 10:05 PM
  3. Help in implementing BIGNUM
    By jack_carver in forum C++ Programming
    Replies: 15
    Last Post: 10-09-2009, 08:22 PM
  4. Math Division Problem
    By cookie in forum C Programming
    Replies: 7
    Last Post: 06-14-2007, 10:34 AM
  5. BigNum Quick Question?
    By gqchynaboy in forum C++ Programming
    Replies: 12
    Last Post: 09-10-2003, 09:06 PM

Tags for this Thread