網(wǎng)上有很多關(guān)于pos機采集發(fā)射模塊,計算機大數(shù)乘法引發(fā)的思考 的知識，也有很多人為大家解答關(guān)于pos機采集發(fā)射模塊的問題，今天pos機之家(m.afbey.com)為大家整理了關(guān)于這方面的知識，讓我們一起來看下吧!
本文目錄一覽：
pos機采集發(fā)射模塊
作者 | dog250
責(zé)編 | 屠敏
出品 | CSDN博客
近日，看了小小的一道學(xué)而思數(shù)學(xué)作業(yè)：
計算
201×33×707+484×636321×33×707+484×6363
我知道肯定是把數(shù)字拆開，配合結(jié)合律完成一種 “巧算” ，之所以稱之為“巧算”，是因為這種算法比通過豎式直接硬算要節(jié)省不少步驟。
但我一下子想不到怎么拆解，我也懶得思考，因為我在思考另一件事。
上題的答案是(各種因數(shù)分解，結(jié)合律)：
原式=67×3×33×707+11×44×9×707=67×3×33×707+11×44×9×707=11×99×707=111×99×7×101=777×9999=7770000?777=7769223
本文結(jié)束了，以下皆為附錄。
通俗來講，一個計算的所有步驟就是一個算法，算法的時間復(fù)雜度其實就是計算的規(guī)模和步驟數(shù)量之間的關(guān)系。
以乘法豎式為例，如果我們將一次十進制一位乘法(即99乘法表的乘法)作為一個步驟，那么兩個n位乘數(shù)相乘需要n的二次方個步驟，其時間復(fù)雜度就是O(n
2) ，但是如果我們采用某種“巧算”，那么計算步驟將會大大減少。
小學(xué)，中學(xué)老師教的各種“巧算”技巧，其宗旨都是減少計算量。我們已經(jīng)承蒙了12年有余的教誨，現(xiàn)在讓我們進入計算機世界。
計算機乘法和我們用豎式計算乘法沒有本質(zhì)區(qū)別?？纯醇臃ㄆ鳎朔ㄆ鞯拈T電路就知道了。
門電路不是我們要關(guān)注的層次，門電路實在是太快了，快到你幾乎無法感知它計算2×3和24890125×98723988的差別。機器是瞬間得到結(jié)果的。
人背下下來了99乘法表，所以人只能一位一位的計算乘法，但計算機不，計算機依靠自身的硬件門電路可以輕而易舉計算出其內(nèi)建數(shù)據(jù)類型乘法，64位的CPU可以輕易計算 0xFFFFFFFFFFFFFFFF 范圍內(nèi)的任意乘法，就好像我們?nèi)祟愑嬎?9乘法表的乘法一樣(我們早就把這個99乘法表背下來了，深刻在了我們的大腦硬件乘法器里)。
然而，超過計算機內(nèi)建類型范圍，計算機便無能為力了。
32位計算機最多只能處理32位的數(shù)字，64位計算機自然只能處理64位數(shù)字，計算機處理超過內(nèi)建數(shù)據(jù)類型范圍的數(shù)字計算的過程稱為 “大數(shù)計算” 。
以64位為例，當(dāng)計算機面對超過64位的數(shù)字乘法時，就好像我們?nèi)祟惷鎸Τ^一位數(shù)的乘法一樣，無法 “一下子” 得到結(jié)果，必須需要某種步驟來計算結(jié)果。這就是說，需要某種算法來進行生成一系列的計算步驟，而 步驟的多少決定了算法的好壞。
舉一個例子，我們嘗試讓計算機計算下面的式子：
23567971209865125789034451795247×12345678909988776655443314719047=?
我們當(dāng)然希望設(shè)計一種巧算的步驟，但在此之前，我們先設(shè)計一種 按部就班的算法，類似我們手算豎式一樣：
人就是這么算的，老老實實地按照十進制99乘法表，一個數(shù)字一個數(shù)字地進行計算，計算過程中處理進位。
手工算豎式人人都會，說這些也無益，上周三下班的班車上，順手?jǐn)]了一個代碼，感覺還好，發(fā)了個朋友圈就想分享出來，本周就休息一天，趕早起來就寫下了這篇文章。
模擬豎式計算的大數(shù)乘法C代碼如下：
// mul.c// gcc mul.c -o mul#include <stdio.h>#include <stdlib.h>#include <string.h>void inlinecarry_add(char *tmp, char num, int index){char tmp_num = 0;char carry;tmp_num = tmp[index] + num;if (tmp_num > 9) {carry = tmp_num / 10;tmp[index] = tmp_num;carry_add(tmp, carry, index-1); // 遞歸進位到底//tmp[index - 1] += carry; // 當(dāng)次進位不能保證tmp[index - 1]+\'0\'是一個字符} else {tmp[index] = tmp_num;}}intmul(char *mul1, char *mul2, char *result){int i, j, mid;int len1, len2, len, pos = 0;char *tmp;len1 = strlen(mul1);len2 = strlen(mul2);len = len1 + len2;tmp = (char *)calloc(len, 1);for (i = 0; i < len2; i++) {for (j = 0; j < len1; j++) {int idx = len - j - i - 1;mid = (mul2[len2 - i - 1] - \'0\') * (mul1[len1 - j - 1] - \'0\');// 這里我是在計算過程中直接遞歸處理進位的，而不是在一輪乘法后再用一個for循環(huán)處理。carry_add(tmp, mid, idx);}// 我不需要在這里用for循環(huán)統(tǒng)一處理進位。// Nothing todo！}i = 0;while(tmp[i++] == 0) pos++;len = len - pos;memcpy(result, tmp + pos, len);free (tmp);for (i = 0; i < len; i++) {result[i] += \'0\';}return 0;}intmain(int argc, char **argv){int len1, len2, i, count;char *m1, *m2, *result;m1 = argv[1];m2 = argv[2];count = atoi(argv[3]);len1 = strlen(m1);len2 = strlen(m2);result = calloc(len1 + len2, 1);// 為了比較速度，這里循環(huán)執(zhí)行count次。for (i = 0; i < count; i++) {memset(result, 0, len1 + len2);mul(m1, m2, result);}printf("%s\", result);free(result);return 0;}
大致就是這個意思。我們試一下這個程序：
[root@localhost ]# ./mul 23567971209865125789034451795247 12345678909988776655443314719047 1290962605116854555936789385617202938185315195749798588574969609
結(jié)果對不對開始我也不知道，不過從算法的執(zhí)行過程上看，以一次簡單乘法計數(shù)，這個算法的時間復(fù)雜度是O(n2)的，這種算法基本是要被斃掉的，所以必須進行優(yōu)化。
哈哈，看到這里，可能很多人以為我要接著講 Karatsuba乘法 以及 快速傅立葉變換了吧。
并不是，因為我不善于寫教程，而且這方面的資源已經(jīng)夠多了，我再寫一遍徒增冗余。我比較善于寫一些思考的過程。
所以，我們按照相對常規(guī)的思路，循序漸進地來思考如何來優(yōu)化程序。
記住，準(zhǔn)則只有一個，即讓計算的步驟變少！
看看上面的代碼，算法完全模仿人類的手工豎式，按照十進制一位乘法來推進計算過程。但是這里面有個根本的問題，猜猜看是什么？
…
一位乘法對于人類而言是可以直接計算的，99乘法表都會背，我們計算4×7的時候，沒有必要擺4排的7，然后數(shù)一數(shù)一共有多少，而是脫口而出28。對于人類而言，超過一位的數(shù)字乘法就屬于大數(shù)了，人們不會把12×89這種計算的結(jié)果背下來，那就需要某種技巧去拆解多位數(shù)字，利用巧算來減少計算步驟了。
換句話說， 超過一位的十進制乘法計算，對于人類而言，就需要動用算法了。
然而，對于計算機卻不是這樣。
64位CPU可以直接計算 0xFFFFFFFFFFFFFFFF 范圍內(nèi)的乘法計算，就像我們計算乘法口訣里的乘法一樣，脫口而出的那種。
這種能力是硬件門電路的可并發(fā)操作決定的，簡單點說，64個引腳可以同時發(fā)射高電平或者低電平，但我們的人腦貌似只能同時發(fā)射一個十進制數(shù)字，這決定了計算機計算多位數(shù)字和我們對待99乘法表是一致的。
看看我們的一個優(yōu)化思路：
對于計算機而言，沒必要一位一位地計算啊，以64位機器而言，每次乘法計算的最大結(jié)果限制在 0xFFFFFFFFFFFFFFFF 就可以了。我們可以按照每8位一組來計算，因為保守計算， 99999999×99999999維持在 0xFFFFFFFFFFFFFFF 范圍內(nèi)。
好了，talk is cheap，下面是C代碼( 這個算法很少見，一般人都是直接利用Karatsuba乘法的，幾乎沒有人利用這種思路來展示分治，所以，希望能仔細看看 )：
// mul2.c// gcc mul2.c -o mul2#include <stdio.h>#include <stdlib.h>#include <string.h>void inlinecarry_add(char *tmp, char num, int index){char tmp_num = 0;char carry;tmp_num = tmp[index] + num;if (tmp_num > 9) {carry = tmp_num / 10;tmp[index] = tmp_num;carry_add(tmp, carry, index-1);} else {tmp[index] = tmp_num;}}// 處理大數(shù)加法intadd(char *s1, int len1, char *s2, int len2, char *result, int *ppos){int i = 0, j = 0, len;char *c;len = len1;if (len2 > len)len = len2;for (i = len - 1; i >= 0; i--) {unsigned char tmp;if (len1 > len2) {tmp = s1[i] - \'0\';if (i > len1 - len2 - 1)tmp += s2[i - (len1 - len2)] - \'0\';} else {tmp = s2[i] - \'0\';if (i > len2 - len1 - 1)tmp += s1[i - (len2 - len1)] - \'0\';}carry_add(result, tmp, i + 1);}*ppos = 1;if (result[0] != 0) {len = len + 1;*ppos = 0;}for (i = 0; i < len + 1; i++) {result[i] += \'0\';}return len;}// 處理大數(shù)乘法intzone_mul(char *mul1, char *mul2, int len, char *result, int result_len){int i, j, n = 0, reslen, totlen, pow1size, pow2size, pos = 0, nblocks = len / 8;unsigned long m1, m2, tmp_res;char str1[10], str2[10], resstr[20];char *pow1, *pow2, *tmp_result;tmp_result = calloc(result_len, 1);pow1 = calloc(len*2, 1);pow2 = calloc(len*2, 1);// 按照每8位十進制數(shù)字進行分割計算。for (i = 0; i < nblocks; i++) {memcpy(str1, mul1 + len - i*8 - 8, 8);m1 = atoi(str1);for (j = 0; j < nblocks; j++) {memcpy(str2, mul2 + len - j*8 - 8, 8);m2 = atoi(str2);tmp_res = m1*m2;// 計算補多少零，也就是乘以10的幾次方pow1size = i*8;pow2size = j*8;totlen = reslen = sprintf(resstr, "%lu", tmp_res);totlen += pow2size;memset(pow2, \'0\', totlen);memcpy(pow2, resstr, reslen);reslen = totlen;totlen += pow1size;memset(pow1, \'0\', totlen);memcpy(pow1, pow2, reslen);memset(result, 0, n + pos);// 累加一次計算結(jié)果，執(zhí)行大數(shù)加法n = add(pow1, totlen, tmp_result, n, result, &pos);memcpy(tmp_result, result + pos, n);}}memset(result, 0, n + pos);memcpy(result, tmp_result, n);free(tmp_result);free(pow1);free(pow2);}intmain(int argc, char **argv){int len1, len2, i = 0, count;char *m1, *m2, *result;m1 = argv[1];m2 = argv[2];count = atoi(argv[3]);len1 = strlen(m1);len2 = strlen(m2);result = calloc(len1 + len2, 1);for (i = 0; i < count; i++) {memset(result, 0, len1 + len2);zone_mul(m1, m2, len1, result, len1 + len2);}printf("%s\", result);free(result);return 0;}
我們來比試一下效果，計算5000次同一個大數(shù)乘法：
[root@localhost ]# time ./mul 119334567890334449388883313579158334567098134455 667908995633221198765432134678040000123411113456 5000079704631383957730438879843848804741889926116047138197998269353980447530720116354515911947726480real 0m1.891suser 0m1.889ssys 0m0.001s[root@localhost ]# time ./mul2 119334567890334449388883313579158334567098134455 667908995633221198765432134678040000123411113456 5000079704631383957730438879843848804741889926116047138197998269353980447530720116354515912427726480real 0m1.475suser 0m1.472ssys 0m0.001s[root@localhost ]#
對于計算機而言， 用計算機力所能及的多位乘法代替人腦的一位乘法 會減少很多的計算步驟，多位乘法對于計算機而言并不苛刻，只要在它的內(nèi)建支持范圍內(nèi)。就像我們計算99乘法一樣，你不會覺得9×9 9\imes 99×9比1×1 1\imes 11×1更難。
但這個優(yōu)化只是動用了計算機和人腦之間的能力差異，我們發(fā)明計算機就是讓它來做計算的，這注定使得它不可能用人類的一位計算方式去做豎式。我的算法保守采用了8位十進制來計算，但這只是最基本的常識，并不算優(yōu)化。
換句話說，這只是開始。
那么，接下來做什么？這才是該考慮的。
重新回想小小的學(xué)而思課后數(shù)學(xué)題：
201×33×707+484×6363
再想想如何來解題。誠然，任何人都知道需要巧算而不是硬算，所謂的巧算就是利用一些初等數(shù)學(xué)知識，比如將201分解成67和3的乘積或200和1的加和。
計算機能不能通過類似因式分解，拆項，結(jié)合律來優(yōu)化計算步驟呢？
很遺憾，計算機沒有智能，目前計算機的所有智能需要程序員來灌入。在將一些策略灌入計算機之前，程序員需要自己先把結(jié)果算出來，然后編程唄…
人可以先把通用公式做出來，然后編程套用即可。
現(xiàn)代數(shù)學(xué)異常強大，我們可以將一個數(shù)字：
進行如下分解：
我們知道，多項式有很多性質(zhì)，如果我們能把一個任意數(shù)字表示成多項式，我們就可以利用這些性質(zhì)了。
這個時候才是引出 Karatsuba算法 的最好時機。
任意兩個數(shù)字x，y我們可以任意取數(shù)字m，然后將其表示為：
x*y都會算吧，結(jié)果就是：
巧嗎？很遺憾，不巧，我們依然還是要處理：
以上的四次乘法，沒有任何節(jié)省。
然而，如果繼續(xù)化簡，就會發(fā)現(xiàn)
之間是有關(guān)系的：
4個乘法減到了3個乘法，其中：
化成了兩個加法和一個乘法，很不錯。
計算機教科書上針對Karatsuba算法的常規(guī)描述是使用遞歸實現(xiàn)，遞歸的退出條件是乘數(shù)稱為一位十進制數(shù)，這是大錯特錯！根本沒有必要讓乘數(shù)稱為一位數(shù)時才退出遞歸，64位機器上兩個乘數(shù)均是8位數(shù)字以內(nèi)時就可以直接相乘而退出遞歸，讓計算機去計算自己力所能及的最大計算量，豈不是最好？
Karatsuba乘法 沒什么大不了的，無非就是利用人類的成果而已。這非常類似于一元二次方程的求解，人類去算的話，可以直接套用公式，而純讓計算機去解，只能一個一個數(shù)字去枚舉嘗試。
Karatsuba乘法我就不再說了。我說點別的。
如果仔細觀察一個多位數(shù)字的多項式表示，我們可以利用的性質(zhì)還有很多，即便是快速傅立葉變換，也不過是其中之一。這就是現(xiàn)代數(shù)學(xué)成果的展示和利用。
但是要知道，即便可以編程實現(xiàn)快速傅立葉變換來計算大數(shù)乘法，也只是利用了人類推導(dǎo)的結(jié)果，換句話說就是套公式，你并沒有利用計算機的優(yōu)勢，而計算機的優(yōu)勢就是可以非?？焖俚匾粋€一個試。
簡單總結(jié)，如果你能把一個數(shù)字：
化為：
那么你就能利用一切關(guān)于多項式的直接結(jié)論去求解類似大數(shù)相乘的問題。這就好比說，讓你求一個方程的解：
你可以利用計算機的快速計算能力一個一個數(shù)字的枚舉，你也可以直接利用韋達定理，求根公式，但是要記住，這不是計算機的能力，這只是計算機程序表達公式的能力。
總而言之， 面對一個大數(shù)計算，手算情況下你覺得怎么操作方便，就把這種操作編程實現(xiàn)，這就是優(yōu)化。
我們真的是細思極恐，我們的所謂現(xiàn)代密碼學(xué)原來完全建立在 “現(xiàn)代計算機不是建立在2048位的基礎(chǔ)之上的” 。
RSA密鑰長度2048位已經(jīng)被證明相當(dāng)安全了，但是數(shù)學(xué)上可以證明的所謂難題如果面對真正的2048位計算機會怎么樣…如果真的有2048位計算機，破解RSA還會很難嗎？內(nèi)建2048位的門電路引腳可以同時發(fā)射2048位的電平信號，可以預(yù)期可以瞬間分解2048位的密鑰，這是多么恐怖的事情。
然而對于此類夢想，2048位計算機難呢，還是量子計算機難呢？經(jīng)理說，篳路藍縷，以啟山林。
【這里需要訂正一下關(guān)于上一段RSA的論述】：
并不是說有了2048位字長的計算機就可以暴力破解RSA了，而是說有了2048位字長的計算機之后，大數(shù)乘法的開銷就被壓縮了，按照nlogn倍壓縮掉了。遍歷2048位解空間的開銷絲毫不受影響，受影響的只是拆解，計算2048位大數(shù)(2048位字長的計算機中不叫大數(shù)了…)的開銷。
換句話說，RSA暴破難題包括兩部分，一部分是數(shù)學(xué)上的，這是由數(shù)學(xué)決定的，另一部分是實現(xiàn)上的計算開銷，這個開銷受計算機結(jié)構(gòu)，字長，時鐘頻率，算法等一系列因素影響，如果實現(xiàn)了2048位字長的計算機，這些開銷將會大大降低，如果是量子計算機，2048位解空間可以并行開解，那就更快了，但是也絲毫沒有動搖RSA算法的數(shù)學(xué)基礎(chǔ)。
突然有人問我一個關(guān)于快速排序為什么快的問題，搜到之前自己的文章，有點想法。
有人問我在同樣O(nlogn) 的時間復(fù)雜度情況下，為什么快速排序比歸并排序快，我沒有辦法證明，但是事實上的原因卻是非常顯然的：
隨機的就是最好的！
詳見：
不知為不知–信息論和最大熵原則 ：https://blog.csdn.net/dog250/article/details/78944526
版權(quán)聲明：本文為CSDN博主「dog250」的原創(chuàng)文章。
以上就是關(guān)于pos機采集發(fā)射模塊,計算機大數(shù)乘法引發(fā)的思考 的知識，后面我們會繼續(xù)為大家整理關(guān)于pos機采集發(fā)射模塊的知識，希望能夠幫助到大家！
