| 24小時(shí)熱門(mén)版塊排行榜 |
| 查看: 2212 | 回復(fù): 14 | |||
| 本帖產(chǎn)生 2 個(gè) 程序強(qiáng)帖 ,點(diǎn)擊這里進(jìn)行查看 | |||
holmescn金蟲(chóng) (正式寫(xiě)手)
|
[交流]
Euler 工程第十六題:2的1000次方的各項(xiàng)和 已有6人參與
|
||
|
這兩天新版開(kāi)通,版里很熱鬧,也就沒(méi)有放題出來(lái)。今天放一個(gè)題吧。 已知2的15次方等于32768,其各項(xiàng)和為:3+2+7+6+8 = 26 。 那么2的1000次方的各項(xiàng)和是多少呢? |
金蟲(chóng) (著名寫(xiě)手)

木蟲(chóng) (正式寫(xiě)手)
|
咳,我突然想到一個(gè)好玩的東西... 對(duì)于一個(gè)數(shù)的大指數(shù)出來(lái)的各個(gè)位數(shù),0-9的概率分布趨向于均勻分布~ 那么我們可以做大致的估算: 2^1000的位數(shù)為 向下取整(1000 * log 2) + 1 = 302 位 對(duì)于每個(gè)位的期望為4.5,然后所有位的和就約等于 302 * 4.5 = 1359 很接近,數(shù)學(xué)真是奇妙啊,哈哈哈~ 嗯,回到正題,這個(gè)題考的是兩個(gè)東西: 1. 大數(shù)乘法 2. 整數(shù)動(dòng)態(tài)規(guī)劃,求最少大數(shù)乘法次數(shù)的步驟 好的C算法在一般PC上應(yīng)該能把運(yùn)算時(shí)間控制在0.5秒以內(nèi),嗯~ PS:土土地思考,從2^31=2147483648開(kāi)始算的話: 2^31 * 2^31 = 2^62 2^62 * 2^62 = 2^124 2^124 * 2 = 2^125 2^125 * 2^125 = 2^250 2^250 * 2^250 = 2^500 2^500 * 2^500 = 2^1000 只需要6次大數(shù)乘法 ,嗯,不確保這是最優(yōu)的分法...不過(guò)這么算已經(jīng)挺快了...[ Last edited by sudo on 2011-5-26 at 22:13 ] |
金蟲(chóng) (著名寫(xiě)手)
|
Originally posted by sudo at 2011-05-26 21:52:34: 咳,我突然想到一個(gè)好玩的東西... 對(duì)于一個(gè)數(shù)的大指數(shù)出來(lái)的各個(gè)位數(shù),0-9的概率分布趨向于均勻分布~ 那么我們可以做大致的估算: 2^1000的位數(shù)為 向下取整(1000 * log 2) + 1 = 302 位 對(duì)于 ... 這么說(shuō)的話,這個(gè)好玩的東西還有另外一個(gè)擴(kuò)展了:散列碼,乘法運(yùn)算的過(guò)程中,除了首位和末位之外,中間的所有位都與因數(shù)的位數(shù)相關(guān),得出的結(jié)果中包含了各種離散的因素,得出的值也必定是均勻分散的。期望值應(yīng)該也非常接近這樣的猜測(cè) ![]() 這題以乘方來(lái)優(yōu)化的話,乘法次數(shù)是少了許多,效率卻不見(jiàn)提高許多,軟件實(shí)現(xiàn)的大數(shù)類(lèi)還是不如硬件geilivable啊…… 突然想實(shí)現(xiàn)一個(gè)補(bǔ)碼運(yùn)算的大數(shù)類(lèi)了 |

木蟲(chóng) (正式寫(xiě)手)
|
Originally posted by huycwork at 2011-05-26 22:29:58: 這么說(shuō)的話,這個(gè)好玩的東西還有另外一個(gè)擴(kuò)展了:散列碼,乘法運(yùn)算的過(guò)程中,除了首位和末位之外,中間的所有位都與因數(shù)的位數(shù)相關(guān),得出的結(jié)果中包含了各種離散的因素,得出的值也必定是均勻分散的。期望值應(yīng) ... 沒(méi)聽(tīng)說(shuō)過(guò)什么硬件實(shí)現(xiàn)了大數(shù)運(yùn)算誒... |
金蟲(chóng) (著名寫(xiě)手)

木蟲(chóng) (正式寫(xiě)手)
木蟲(chóng) (知名作家)

金蟲(chóng) (著名寫(xiě)手)
|
Originally posted by sudo at 2011-05-26 22:44:24: =,=這個(gè)不能算“大數(shù)”吧... 把寄存器調(diào)大一些不就可以了嘛~ 不過(guò)這電路板就復(fù)雜了,嚴(yán)重懷疑散熱性能 ![]() 我最近就實(shí)現(xiàn)了一個(gè)基于位的模板類(lèi),效率很不高啊,就是因?yàn)闇p少乘法次數(shù)引入了負(fù)數(shù),整個(gè)代碼都復(fù)雜了。 |

金蟲(chóng) (著名寫(xiě)手)

| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 302求調(diào)劑一志愿北航070300,本科鄭大化學(xué) +8 | 圣日耳曼條 2026-04-01 | 11/550 |
|
|---|---|---|---|---|
|
[考研] 生物學(xué)308分求調(diào)劑(一志愿華東師大) +4 | 相信必會(huì)光芒萬(wàn)?/a> 2026-03-31 | 4/200 |
|
|
[考研] 292分,材料與化工,申請(qǐng)調(diào)劑 +18 | 程晴之 2026-04-01 | 20/1000 |
|
|
[考研] 266求調(diào)劑 +7 | 陽(yáng)陽(yáng)哇塞 2026-04-01 | 7/350 |
|
|
[考研] 0703化學(xué)338求調(diào)劑! +8 | Zuhui0306 2026-03-26 | 9/450 |
|
|
[考研] 環(huán)境工程297分求調(diào)劑一志愿杭高院 +10 | GENJIOW 2026-03-31 | 11/550 |
|
|
[考研] 總分343,求生物學(xué)調(diào)劑 +6 | 深刻的凱撒 2026-03-26 | 6/300 |
|
|
[考研] 一志愿南昌大學(xué)324求調(diào)劑 +10 | hanamiko 2026-04-01 | 10/500 |
|
|
[考研] 358求調(diào)劑 +3 | 王向陽(yáng)花 2026-03-31 | 3/150 |
|
|
[考研] 336材料求調(diào)劑 +10 | 陳瀅瑩 2026-03-26 | 12/600 |
|
|
[考研] 江蘇蘇北高校誠(chéng)邀調(diào)劑同學(xué) +3 | zzll406 2026-03-31 | 3/150 |
|
|
[考研] 一志愿哈爾濱工業(yè)大學(xué)材料與化工方向336分 +13 | 辰沐5211314 2026-03-26 | 13/650 |
|
|
[考研] 生物考研337分求調(diào)劑 +4 | cgxin 2026-03-30 | 6/300 |
|
|
[考研] 334求調(diào)劑 +7 | Trying] 2026-03-31 | 7/350 |
|
|
[考研] 本科211總分289,08工學(xué)真心求調(diào)劑 +3 | utopiaE 2026-03-30 | 3/150 |
|
|
[考研] 281求調(diào)劑 +5 | 亞克西good 2026-03-26 | 7/350 |
|
|
[考研] 0703化學(xué)求調(diào)劑 +6 | 丹青奶蓋 2026-03-26 | 8/400 |
|
|
[考研] 298求調(diào)劑 +4 | 種圣賜 2026-03-28 | 4/200 |
|
|
[考研] 調(diào)劑考研 +3 | 王杰一 2026-03-29 | 3/150 |
|
|
[考研] 316求調(diào)劑 +7 | 江辭666 2026-03-26 | 7/350 |
|