经典面试题# JobHunting - 待字闺中
d*g
1 楼
code: multiplication algorithm for a long long integer,(you can not store
the integer with int or even long, unsinged long)
the integer with int or even long, unsinged long)
c*2
2 楼
How about this:
1) count how many digits are in the numbers,
let's say it's 11 digits
2) reduce it:
a=long long (11 digits)
double b=a/10^10;
then easy double operations.
In short, do it in units of billions.
1) count how many digits are in the numbers,
let's say it's 11 digits
2) reduce it:
a=long long (11 digits)
double b=a/10^10;
then easy double operations.
In short, do it in units of billions.
d*g
3 楼
double b=a/10^10;
这是啥意思?b = a/(10^10)? 10^10不会overflow吗?
这是啥意思?b = a/(10^10)? 10^10不会overflow吗?
c*t
4 楼
用数组存每一位
然后怎么人工手算的就怎么让机器算
不难，但麻烦
然后怎么人工手算的就怎么让机器算
不难，但麻烦
w*p
5 楼
http://en.wikipedia.org/wiki/Multiplication_algorithm
an implementation of the "lattice mul":
#include
#include
void box(const char* v1, const char* v2)
{
size_t len1 = strlen(v1);
size_t len2 = strlen(v2);
size_t lres = len1 + len2;
char res[lres+1];
size_t i1, i2;
for (i1 = 0; i1 < lres; i1 ++)
res[i1] = 0;
res[lres] = '\0';
for (i1 = 0; i1 < len1; i1 ++)
for (i2 = 0; i2 < len2; i2 ++)
{
int int1 = (int) (v1[len1-1-i1] - '0');
int int2 = (int) (v2[len2-1-i2] - '0');
int mul = int1 * int2;
int low = mul % 10;
int hi = mul / 10;
int id_cur = lres -1 - (i1 + i2);
int id_nex = lres -1 - (i1 + i2 + 1);
res[id_cur] += low;
if (res[id_cur] > 9) {
int orig = res[id_cur];
res[id_cur] = orig % 10;
res[id_nex] += orig / 10;
}
res[id_nex] += hi;
}
for (i1 = 0; i1 < lres; i1 ++)
{
res[i1] += '0';
}
printf("%s * %s = %s\n", v1, v2, res);
}
int main()
{
box("
1207397946390401677949638206528245302745615036902178697298778934371316357537
5237658526390429412084288966270827958533621464451773788627863089944207706329
0998690843220400316891982157493412801783849895569252590717413908015748795899
5958184110014495739101806800496574711306203902212886996941676813558767333626
3202437205906835381185025353829163034552992969644234543757438866275748465878
2853192036736192857421195735185925461104285506376070431067736870675936469670
8931534583888132827569712761871030787395122548122039401034834965998864767043
2954894528523238003554416867690542284204378688409835426338087382885739886924
3437491289374741283691176692248245207895876853791038511282636969664931731925
4618618456778672272911551222166385253113414678647969207629866770159408840582
8518626102191374936033368538152676102229355189036891758148650050556520071091
1749995630361568122922866923699927425639127099166676140580055271946931821190
2847827119351536512380585826188813072435808215687256385615595263740080913173
6320693387665234021156401327238318975322220538174897214651311243215025416775
3065033274500642455885000939409036352233206752891688446233252803923397963997
2331735967816115537830948787180019114081652360329243140776149356095852379793
2110573495200859969216468309237962356885619848156317497282267164678490054229
1688715956644751233199097926041053974829664236830510838090940213007400760961
5674075805495729131670380261192063682596352022924643744806814860803697460881
1720691782022528194280636785223166696182576006086315115631909185643460330555
2924570726682621070951514399996106958333323335754056198053400393161680163412
0370372215511776533239620463083705431223355741608270532788457362247054876028
9990711556256143895857566325884553185371656038211859220355446749229511426985
7663952513924905413937455428714104157573955384318925844813206817047563136931
5517454723094015807286627008738153109889590386711400517903665094138138642136
2904144549270337767136761847377517292559394830217672821871024896783118663669
8300503045941245563898013572758467460432084027337104208119278091128026541234
3918943837897635324168617041578189390812421463726076477053222897095161775029
9168831497486720687737409629187038832575163168113376967623547540072120554617
9198509188354635154379644527014303662791508578011119938502666071818378023910
5123889148035219288545748106017952617959418912967534358206314364870883049572
8900238073772520463146915035687132988033531548863897474721371713958727424152
5896604535448935073087212283038050697261259402288416796712365430807168763978
6652731386764010151185424921007187966697788877044362177608237257323458618754
8039521155165331798433840546611404477235993376926555966504333430669486763084
9803931583589908578986890550316822852826630958766793128709600171616858377595
7120665070303213833108795470036780550646991807161370044058242870294132454982
6590410056227949312863094116671448402992002832109232098675108728723890865273
830172766844914542170010496732115439071408596182183166421684536942722561", "
1207397946390401677949638206528245302745615036902178697298778934371316357537
5237658526390429412084288966270827958533621464451773788627863089944207706329
0998690843220400316891982157493412801783849895569252590717413908015748795899
5958184110014495739101806800496574711306203902212886996941676813558767333626
3202437205906835381185025353829163034552992969644234543757438866275748465878
2853192036736192857421195735185925461104285506376070431067736870675936469670
8931534583888132827569712761871030787395122548122039401034834965998864767043
2954894528523238003554416867690542284204378688409835426338087382885739886924
3437491289374741283691176692248245207895876853791038511282636969664931731925
4618618456778672272911551222166385253113414678647969207629866770159408840582
8518626102191374936033368538152676102229355189036891758148650050556520071091
1749995630361568122922866923699927425639127099166676140580055271946931821190
2847827119351536512380585826188813072435808215687256385615595263740080913173
6320693387665234021156401327238318975322220538174897214651311243215025416775
3065033274500642455885000939409036352233206752891688446233252803923397963997
2331735967816115537830948787180019114081652360329243140776149356095852379793
2110573495200859969216468309237962356885619848156317497282267164678490054229
1688715956644751233199097926041053974829664236830510838090940213007400760961
5674075805495729131670380261192063682596352022924643744806814860803697460881
1720691782022528194280636785223166696182576006086315115631909185643460330555
2924570726682621070951514399996106958333323335754056198053400393161680163412
0370372215511776533239620463083705431223355741608270532788457362247054876028
9990711556256143895857566325884553185371656038211859220355446749229511426985
7663952513924905413937455428714104157573955384318925844813206817047563136931
5517454723094015807286627008738153109889590386711400517903665094138138642136
2904144549270337767136761847377517292559394830217672821871024896783118663669
8300503045941245563898013572758467460432084027337104208119278091128026541234
3918943837897635324168617041578189390812421463726076477053222897095161775029
9168831497486720687737409629187038832575163168113376967623547540072120554617
9198509188354635154379644527014303662791508578011119938502666071818378023910
5123889148035219288545748106017952617959418912967534358206314364870883049572
8900238073772520463146915035687132988033531548863897474721371713958727424152
5896604535448935073087212283038050697261259402288416796712365430807168763978
6652731386764010151185424921007187966697788877044362177608237257323458618754
8039521155165331798433840546611404477235993376926555966504333430669486763084
9803931583589908578986890550316822852826630958766793128709600171616858377595
7120665070303213833108795470036780550646991807161370044058242870294132454982
6590410056227949312863094116671448402992002832109232098675108728723890865273
830172766844914542170010496732115439071408596182183166421684536942722561");
}
an implementation of the "lattice mul":
#include
#include
void box(const char* v1, const char* v2)
{
size_t len1 = strlen(v1);
size_t len2 = strlen(v2);
size_t lres = len1 + len2;
char res[lres+1];
size_t i1, i2;
for (i1 = 0; i1 < lres; i1 ++)
res[i1] = 0;
res[lres] = '\0';
for (i1 = 0; i1 < len1; i1 ++)
for (i2 = 0; i2 < len2; i2 ++)
{
int int1 = (int) (v1[len1-1-i1] - '0');
int int2 = (int) (v2[len2-1-i2] - '0');
int mul = int1 * int2;
int low = mul % 10;
int hi = mul / 10;
int id_cur = lres -1 - (i1 + i2);
int id_nex = lres -1 - (i1 + i2 + 1);
res[id_cur] += low;
if (res[id_cur] > 9) {
int orig = res[id_cur];
res[id_cur] = orig % 10;
res[id_nex] += orig / 10;
}
res[id_nex] += hi;
}
for (i1 = 0; i1 < lres; i1 ++)
{
res[i1] += '0';
}
printf("%s * %s = %s\n", v1, v2, res);
}
int main()
{
box("
1207397946390401677949638206528245302745615036902178697298778934371316357537
5237658526390429412084288966270827958533621464451773788627863089944207706329
0998690843220400316891982157493412801783849895569252590717413908015748795899
5958184110014495739101806800496574711306203902212886996941676813558767333626
3202437205906835381185025353829163034552992969644234543757438866275748465878
2853192036736192857421195735185925461104285506376070431067736870675936469670
8931534583888132827569712761871030787395122548122039401034834965998864767043
2954894528523238003554416867690542284204378688409835426338087382885739886924
3437491289374741283691176692248245207895876853791038511282636969664931731925
4618618456778672272911551222166385253113414678647969207629866770159408840582
8518626102191374936033368538152676102229355189036891758148650050556520071091
1749995630361568122922866923699927425639127099166676140580055271946931821190
2847827119351536512380585826188813072435808215687256385615595263740080913173
6320693387665234021156401327238318975322220538174897214651311243215025416775
3065033274500642455885000939409036352233206752891688446233252803923397963997
2331735967816115537830948787180019114081652360329243140776149356095852379793
2110573495200859969216468309237962356885619848156317497282267164678490054229
1688715956644751233199097926041053974829664236830510838090940213007400760961
5674075805495729131670380261192063682596352022924643744806814860803697460881
1720691782022528194280636785223166696182576006086315115631909185643460330555
2924570726682621070951514399996106958333323335754056198053400393161680163412
0370372215511776533239620463083705431223355741608270532788457362247054876028
9990711556256143895857566325884553185371656038211859220355446749229511426985
7663952513924905413937455428714104157573955384318925844813206817047563136931
5517454723094015807286627008738153109889590386711400517903665094138138642136
2904144549270337767136761847377517292559394830217672821871024896783118663669
8300503045941245563898013572758467460432084027337104208119278091128026541234
3918943837897635324168617041578189390812421463726076477053222897095161775029
9168831497486720687737409629187038832575163168113376967623547540072120554617
9198509188354635154379644527014303662791508578011119938502666071818378023910
5123889148035219288545748106017952617959418912967534358206314364870883049572
8900238073772520463146915035687132988033531548863897474721371713958727424152
5896604535448935073087212283038050697261259402288416796712365430807168763978
6652731386764010151185424921007187966697788877044362177608237257323458618754
8039521155165331798433840546611404477235993376926555966504333430669486763084
9803931583589908578986890550316822852826630958766793128709600171616858377595
7120665070303213833108795470036780550646991807161370044058242870294132454982
6590410056227949312863094116671448402992002832109232098675108728723890865273
830172766844914542170010496732115439071408596182183166421684536942722561", "
1207397946390401677949638206528245302745615036902178697298778934371316357537
5237658526390429412084288966270827958533621464451773788627863089944207706329
0998690843220400316891982157493412801783849895569252590717413908015748795899
5958184110014495739101806800496574711306203902212886996941676813558767333626
3202437205906835381185025353829163034552992969644234543757438866275748465878
2853192036736192857421195735185925461104285506376070431067736870675936469670
8931534583888132827569712761871030787395122548122039401034834965998864767043
2954894528523238003554416867690542284204378688409835426338087382885739886924
3437491289374741283691176692248245207895876853791038511282636969664931731925
4618618456778672272911551222166385253113414678647969207629866770159408840582
8518626102191374936033368538152676102229355189036891758148650050556520071091
1749995630361568122922866923699927425639127099166676140580055271946931821190
2847827119351536512380585826188813072435808215687256385615595263740080913173
6320693387665234021156401327238318975322220538174897214651311243215025416775
3065033274500642455885000939409036352233206752891688446233252803923397963997
2331735967816115537830948787180019114081652360329243140776149356095852379793
2110573495200859969216468309237962356885619848156317497282267164678490054229
1688715956644751233199097926041053974829664236830510838090940213007400760961
5674075805495729131670380261192063682596352022924643744806814860803697460881
1720691782022528194280636785223166696182576006086315115631909185643460330555
2924570726682621070951514399996106958333323335754056198053400393161680163412
0370372215511776533239620463083705431223355741608270532788457362247054876028
9990711556256143895857566325884553185371656038211859220355446749229511426985
7663952513924905413937455428714104157573955384318925844813206817047563136931
5517454723094015807286627008738153109889590386711400517903665094138138642136
2904144549270337767136761847377517292559394830217672821871024896783118663669
8300503045941245563898013572758467460432084027337104208119278091128026541234
3918943837897635324168617041578189390812421463726076477053222897095161775029
9168831497486720687737409629187038832575163168113376967623547540072120554617
9198509188354635154379644527014303662791508578011119938502666071818378023910
5123889148035219288545748106017952617959418912967534358206314364870883049572
8900238073772520463146915035687132988033531548863897474721371713958727424152
5896604535448935073087212283038050697261259402288416796712365430807168763978
6652731386764010151185424921007187966697788877044362177608237257323458618754
8039521155165331798433840546611404477235993376926555966504333430669486763084
9803931583589908578986890550316822852826630958766793128709600171616858377595
7120665070303213833108795470036780550646991807161370044058242870294132454982
6590410056227949312863094116671448402992002832109232098675108728723890865273
830172766844914542170010496732115439071408596182183166421684536942722561");
}
d*u
6 楼
FFT
d*j
7 楼
这个是正解！
Wiki里面的伪代码非常经典：
multiply(a[0..n−1], b[0..n−1]) // Arrays representing the binary
representations
x ← 0
for i from 0 to 2n−2
for j from max(0,i+1−n) to min(i,n−1)
k ← i − j
x ← x + (a[j] × b[k])
result[i] ← x mod 2
x ← floor(x/2)
return result[];
其中a, b [0,..n-1]表示从低位到高位的顺序，计算的顺序也是从低到高
改成10进制也很简单，x mod 2 改成 x%10, x/2-> x/10 即可。
注意，最后的进位上面代码里面没处理，需要处理一下。
自己练一下，还是很好玩的，特别是里面j的取值范围。
此外，如果a和b的数量级不一样，比如a是n位数，b是m位数，再写这个程序就更刺激了。
发信人: westcamp (西草), 信区: JobHunting
标 题: Re: 经典面试题
发信站: BBS 未名空间站 (Wed Nov 24 11:56:12 2010, 美东)
http://en.wikipedia.org/wiki/Multiplication_algorithm
Wiki里面的伪代码非常经典：
multiply(a[0..n−1], b[0..n−1]) // Arrays representing the binary
representations
x ← 0
for i from 0 to 2n−2
for j from max(0,i+1−n) to min(i,n−1)
k ← i − j
x ← x + (a[j] × b[k])
result[i] ← x mod 2
x ← floor(x/2)
return result[];
其中a, b [0,..n-1]表示从低位到高位的顺序，计算的顺序也是从低到高
改成10进制也很简单，x mod 2 改成 x%10, x/2-> x/10 即可。
注意，最后的进位上面代码里面没处理，需要处理一下。
自己练一下，还是很好玩的，特别是里面j的取值范围。
此外，如果a和b的数量级不一样，比如a是n位数，b是m位数，再写这个程序就更刺激了。
发信人: westcamp (西草), 信区: JobHunting
标 题: Re: 经典面试题
发信站: BBS 未名空间站 (Wed Nov 24 11:56:12 2010, 美东)
http://en.wikipedia.org/wiki/Multiplication_algorithm
相关阅读
Youtube(Google) team match 求大侠收留什么放不放水bar不bar的老中没救了Facebook 2017暑期实习 求收留 (PhD Team Match)startup ISO option请教leetcode 的题目怎么增加得这么快说说我的一次面试Linkedin现在的包裹/股票如何?请问抽中之后H1B的起始终止时间?可以辞职了吗？去做drug test还要拍照片？川普宣布以后只用tweet发布公告，Twitter股票要大涨 (转载)有木有人了解Cybercoders这个公司？怎么练习multi-threading，平常工作都是用Java框架job open Hardware engineer Intel Folsom & Boise【南加内推】Big data SWEoracle裁员2000Avago (现在的Broadcom) 每年RSU refresh会有多少？求问一道U家的算法设计题奇怪的一个leetcode题