大整数乘法——格子算法

大家好，欢迎来到IT知识分享网。

格子乘法是一种最早见于十三世纪阿拉伯，十四世纪流行于欧洲的乘法[1]，是一种利用带斜线的格子进行多位数的乘法，意大利人称为威尼斯方格乘法。格子乘法在明朝初期传入中国，首先出现在景泰元年数学家吴敬所著《九章详注比类算法大全》，称为写算[2]。后来程大位《算法统宗》也阐述了这种铺地锦算法[2]。印度数学史家Datta和Singh认为不能确定格子乘法起源于印度或是舶来品；格子乘法最早见于印度一部1545年的数学著作，而在13、14世纪已经出现在阿拉伯数学著作了[3]， // test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <stdio.h> #include <string.h> #define uint8_t unsigned char  #define uint32_t unsigned long #define int8_t char #define int32_t long uint8_t numadd1[100] = { 
   '1','0','0','0' }; uint8_t numadd2[100] ={ 
   '1','0','0','0','0' }; uint8_t numadd[102] = { 
   0}; uint32_t CAL_len(uint8_t * buf) { 
    uint32_t len =0; if(buf == NULL) { 
    printf("Cal len input error\r\n"); return 0; } while(*buf != '\0') { 
    len++; buf++; } return len; } bool Ascii_to_dec(uint8_t * arr ,uint8_t *arr_out) { 
    uint32_t len =0; uint8_t *buf_in = arr; uint8_t *buf_out = arr_out; if(buf_in == NULL) { 
    printf("CAscii_to_dec input error\r\n"); return false; } printf( "\r\n" ); while(*buf_in != '\0') { 
    if( 0x30> (*buf_in) || 0x39< (*buf_in)) { 
    printf( "Ascii_to_dec not in \'0\' -\'9\'" ); return false ; } else { 
    *buf_out = *buf_in - 0x30; printf( "buf_out = %d\r\n" , *buf_out ); } buf_in++; buf_out++; } return true; } bool dec_to_ascii(uint8_t * arr ,uint8_t *arr_out , uint32_t len) { 
    uint8_t *buf_in = arr; uint8_t *buf_out = arr_out; if(buf_in == NULL) { 
    printf("CAscii_to_dec input error\r\n"); return false; } while(len--) { 
    if(*buf_in >=0 && *buf_in <=9) { 
    *buf_out = *buf_in + 0x30; } else { 
    *buf_out = *buf_in; } buf_in++; buf_out++; } return true; } void chage_arr(uint8_t * buf , uint32_t len) { 
    uint32_t i = 0; uint8_t path = 0; for(i = 0 ; i < len/2 ; i++) { 
    path = buf[i] ; buf[i] = buf[len -1-i]; buf[len -1-i] = path; } } /格子乘法* -------- | /| | x / | | / | | / y | | / | |/ | -------- / void Multiplication(uint8_t *arg1 , uint8_t *arg2 , uint8_t *out) { 
    uint8_t *buf = out; uint32_t x_idx = 0; uint32_t y_idx = 0; int32_t i = 0,j = 0,k = 0; uint8_t path_num = 0; uint8_t up = 0; //获取格子的长和宽 x_idx = CAL_len(arg1); y_idx = CAL_len(arg2); //交换到格子算法位置 chage_arr(arg1 ,x_idx); chage_arr(arg2 ,y_idx); //换成10进制 if(Ascii_to_dec(arg1,arg1) == false) { 
    return ; } if(Ascii_to_dec(arg2,arg2) == false) { 
    return ; } //开始计算 for( i = 0; i < x_idx +y_idx ; i++) //i 代表计算出来每一个位置的值 { 
    path_num = 0; up = 0; //x轴 if( i < x_idx) { 
    j = i;k = 0; for( j = i; (j>=0) &&(k<y_idx); j-- ,k++ )//下三角之和 { 
    path_num+= ((arg1[j]*arg2[k])%10); up += path_num/10; path_num %=10; } j = i;k = 0; for( ; j>0 &&k<y_idx ; j-- , k++)//上三角之和 { 
    path_num+= arg1[j-1]*arg2[k]/10; up+=path_num/10; path_num%=10; } buf[i] += path_num; buf[i+1] = up; } else //y轴 { 
    j = x_idx-1; k = i-x_idx; for( ; k< y_idx &&j>0 ; j-- , k++)//上三角之和 { 
    path_num+= arg1[j]*arg2[k]/10; up+=path_num/10; path_num%10; } j = x_idx-1; k = i-x_idx+1; for( ; k< y_idx &&j>=0 ; j-- , k++)//下三角之和 { 
    path_num+= arg1[j]*arg2[k]%10; up+=path_num/10; path_num%=10; } buf[i] += path_num; buf[i+1] = up; } } for(i =x_idx+y_idx-1 ; i>=0 ; i-- ) { 
    if(buf[i] != 0) break; printf("Multiplication %d i = %d \r\n ",buf[i] , i); } chage_arr(buf , i+1); dec_to_ascii(buf ,buf,i+1 ); } int main(int argc, char* argv[]) { 
    uint8_t i=0; Multiplication(numadd1 , numadd2 ,numadd); printf("%s",numadd); while(1) { 
   } return 0; }