繁體瀏覽工具設為首頁收藏本站
 找回密碼 或 安全提問
 註冊
|註冊|登錄

伊莉討論區

搜索
請尊重及感激所有版主付出和奉獻尊貴會員無限觀看附件圖片尊貴會員無限看帖不用回覆
伊莉討論區 › 論壇 › 電腦資訊 › 電腦程式設計 › C & C++ 語言 › 使用牛頓迭代法計算整數的平方根
火影忍者刀劍神域我的英雄催眠3d中出幼女
漫無蹤影アリサグストップ家出娘種洗脳悪堕告五人apak 237
休閒聊天興趣交流學術文化旅遊交流飲食交流家庭事務PC GAMETV GAME
熱門線上其他線上感情感性寵物交流家族門派動漫交流貼圖分享BL/GL
音樂世界影視娛樂女性頻道潮流資訊BT下載區GB下載區下載分享短片
電腦資訊數碼產品手機交流交易廣場網站事務長篇小說體育運動時事經濟
上班一族博彩娛樂

[繁]怪人的沙拉碗03-
[繁]魔法科高中的劣等
衝進中橫水溝 紅牌重

[繁]老夫老妻重返青春
[繁]無職轉生 第二季1
(4月新番)[簡]被稱為
C & C++ 語言C# 語言Visual Basic 語言PHP 語言JAVA 語言
返回列表發新帖

查看: 4766|回復: 9
打印上一主題下一主題

[教學]使用牛頓迭代法計算整數的平方根[複製鏈接]

kym3

Rank: 1

帖子
126
積分
87 點
潛水值
4060 米
跳轉到指定樓層
樓主
發表於 2014-5-17 06:32 PM|只看該作者|倒序瀏覽
上傳頭像立即獲得 1 點積分。
要求計算整數的平方根，返回值也是整數（向下取整）
例如：
輸入100 輸出10
輸入8 輸出2
輸入1 輸出1
輸入0 輸出0...
瀏覽完整內容，請先 註冊 或 登入會員

點評

snowflying 如果是向下取整數，那麼可以用二分逼近法搜答案  發表於 2014-5-18 02:56 PM
分享分享0收藏收藏0支持支持0
分享使你變得更實在，可以使其他人感到快樂，分享是我們的動力。今天就來分享你的資訊、圖片或檔案吧。

使用道具檢舉

chevylin0802

Rank: 4Rank: 4Rank: 4Rank: 4

帖子
7565
積分
4321 點
潛水值
34960 米
頭香
發表於 2014-5-17 06:56 PM|只看該作者
伊莉影片
本帖最後由 chevylin0802 於 2014-5-17 07:12 PM 編輯

請養成好習慣

C就是C
C++就是C++

不要混用

因為我們很討厭這種壞習慣的工程師
為了自己的方便
可是也沒有真正方便到哪裏去
卻很喜歡搞混用

像我現在要找一個真正懂得寫Linux driver的人
都要重新教起
要花好幾個月去調整回他的壞習慣
...
瀏覽完整內容，請先 註冊 或 登入會員

點評

TKCS 學校從來就沒在培養寫程式的人才 還不都要出來自己學  發表於 2014-5-23 08:13 PM
系統已重置禁訪用戶到普通用戶和密碼一次
若登入不正常或變回訪客狀態，請先刪除COOKIE再登入。

使用道具檢舉

kym3

Rank: 1

帖子
126
積分
87 點
潛水值
4060 米
3樓
發表於 2014-5-17 10:25 PM|只看該作者
若有安裝色情守門員，可用無界、自由門等軟件瀏覽伊莉。或使用以下網址瀏覽伊莉: http://www.eyny.com:81/index.php
chevylin0802 發表於 2014-5-17 06:56 PM
下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

請養成好習慣

C就是C

那您說這段代碼該怎麼改？
如果瀏覽伊莉時速度太慢或無法連接，可以使用其他分流瀏覽伊莉，www01.eyny.com(02,03)。

使用道具檢舉

kym3

Rank: 1

帖子
126
積分
87 點
潛水值
4060 米
4樓
發表於 2014-5-18 11:47 PM|只看該作者
如果你覺得伊莉做得不錯，那就不要再猶疑了。今天就贊助和支持我們，立即行動！我們需要你的一點力量喔。
@snowflying 嗯，確實二分查找也行。但是迭代速度不一樣。我這個的迭代速度比二分查找高一階，是平方收斂。往往要有權衡，迭代速度快的，每一次迭代要進行的運算就更多。實際哪種快，得測。
分享使你變得更實在，可以使其他人感到快樂，分享是我們的動力。今天就來分享你的資訊、圖片或檔案吧。

使用道具檢舉

chevylin0802

Rank: 4Rank: 4Rank: 4Rank: 4

帖子
7565
積分
4321 點
潛水值
34960 米
5樓
發表於 2014-5-26 01:19 PM|只看該作者
所有積分大於負-100的壞孩子，將可獲得重新機會成為懲罰生，權限跟幼兒生一樣。
本帖最後由 chevylin0802 於 2014-5-26 01:52 PM 編輯

像這種的一般都是採用泰勒展開式來做會最快

fabs 也好
floor也好
都需要用浮點數來計算
這是泰勒展開式的原型
f(x) = 1 + (x-1)/2 - (1/4)((x-1)^2/2!) +(3/8)((x-1)^3)/3!)-15/16((x-1)^4)/4!).......
既然要求算的是近似的整數
那麼我們應該盡可能使用整數四則運算法來做會比較妥
...
瀏覽完整內容，請先 註冊 或 登入會員





點評

chevylin0802 遇到你講的狀況, 應該要反組譯成組合語言來看才會知道  發表於 2014-5-27 10:10 AM
chevylin0802 我想慢是因為它被編譯成使用fpu指令做的關係, 不過一般來說應該不可能  發表於 2014-5-27 10:09 AM
EdisonX fabs 不自己寫是有些 compiler 自己寫反而慢 ； floor 用強制轉型是可能會導致 ov 問題，當然這裡可能不會發生。  發表於 2014-5-27 09:50 AM
系統已重置禁訪用戶到普通用戶和密碼一次
若對尊貴或贊助會員有任何疑問，歡迎向我們查詢。我們的即時通或MSN: admin@eyny.com

使用道具檢舉

EdisonX

Rank: 3Rank: 3Rank: 3

帖子
328
積分
2651 點
潛水值
10849 米
6樓
發表於 2014-5-27 09:47 AM|只看該作者
若瀏覽伊莉的時侯發生問題或不正常情況，請使用Internet Explorer(I.E)。
binary search and create table
  1. #include <stdint.h>

  3. const uint16_t squares[] = {
  4.     0, 1, 4, 9,
  5.     16, 25, 36, 49,
  6.     64, 81, 100, 121,
  7.     144, 169, 196, 225,
  8.     256, 289, 324, 361,
  9.     400, 441, 484, 529,
  10.     576, 625, 676, 729,
  11.     784, 841, 900, 961,
  12.     1024, 1089, 1156, 1225,
  13.     1296, 1369, 1444, 1521,
  14.     1600, 1681, 1764, 1849,
  15.     1936, 2025, 2116, 2209,
  16.     2304, 2401, 2500, 2601,
  17.     2704, 2809, 2916, 3025,
  18.     3136, 3249, 3364, 3481,
  19.     3600, 3721, 3844, 3969,
  20.     4096, 4225, 4356, 4489,
  21.     4624, 4761, 4900, 5041,
  22.     5184, 5329, 5476, 5625,
  23.     5776, 5929, 6084, 6241,
  24.     6400, 6561, 6724, 6889,
  25.     7056, 7225, 7396, 7569,
  26.     7744, 7921, 8100, 8281,
  27.     8464, 8649, 8836, 9025,
  28.     9216, 9409, 9604, 9801,
  29.     10000, 10201, 10404, 10609,
  30.     10816, 11025, 11236, 11449,
  31.     11664, 11881, 12100, 12321,
  32.     12544, 12769, 12996, 13225,
  33.     13456, 13689, 13924, 14161,
  34.     14400, 14641, 14884, 15129,
  35.     15376, 15625, 15876, 16129,
  36.     16384, 16641, 16900, 17161,
  37.     17424, 17689, 17956, 18225,
  38.     18496, 18769, 19044, 19321,
  39.     19600, 19881, 20164, 20449,
  40.     20736, 21025, 21316, 21609,
  41.     21904, 22201, 22500, 22801,
  42.     23104, 23409, 23716, 24025,
  43.     24336, 24649, 24964, 25281,
  44.     25600, 25921, 26244, 26569,
  45.     26896, 27225, 27556, 27889,
  46.     28224, 28561, 28900, 29241,
  47.     29584, 29929, 30276, 30625,
  48.     30976, 31329, 31684, 32041,
  49.     32400, 32761, 33124, 33489,
  50.     33856, 34225, 34596, 34969,
  51.     35344, 35721, 36100, 36481,
  52.     36864, 37249, 37636, 38025,
  53.     38416, 38809, 39204, 39601,
  54.     40000, 40401, 40804, 41209,
  55.     41616, 42025, 42436, 42849,
  56.     43264, 43681, 44100, 44521,
  57.     44944, 45369, 45796, 46225,
  58.     46656, 47089, 47524, 47961,
  59.     48400, 48841, 49284, 49729,
  60.     50176, 50625, 51076, 51529,
  61.     51984, 52441, 52900, 53361,
  62.     53824, 54289, 54756, 55225,
  63.     55696, 56169, 56644, 57121,
  64.     57600, 58081, 58564, 59049,
  65.     59536, 60025, 60516, 61009,
  66.     61504, 62001, 62500, 63001,
  67.     63504, 64009, 64516, 65025
  68. };

  70. inline int isqrt(uint16_t x) {
  71.     const uint16_t *p = squares;

  73.     if (p[128] <= x) p += 128;
  74.     if (p[ 64] <= x) p +=  64;
  75.     if (p[ 32] <= x) p +=  32;
  76.     if (p[ 16] <= x) p +=  16;
  77.     if (p[  8] <= x) p +=   8;
  78.     if (p[  4] <= x) p +=   4;
  79.     if (p[  2] <= x) p +=   2;
  80.     if (p[  1] <= x) p +=   1;

  82.     return p - squares;
  83. }
複製代碼
this code doesn't mean the best....
瀏覽完整內容，請先 註冊 或 登入會員

點評

gerry0622 先算完也是個聰明的方法，空間換取時間嘛！很多巨量資料的查詢也是預先計算的  發表於 2014-5-29 10:54 AM
chevylin0802 這幾年機器人學恐怕會成為潮流之一........  發表於 2014-5-27 02:04 PM
如果沒有明天
我想見你最後一面
如果重複性登入後自動登出，請先刪除所有Cookie和舊網頁再登入。

使用道具檢舉

af006350

Rank: 6Rank: 6Rank: 6Rank: 6Rank: 6Rank: 6

帖子
86
積分
1471 點
潛水值
43543 米
7樓
發表於 2015-12-30 10:57 AM|只看該作者
上傳頭像立即獲得 1 點積分。
本帖最後由 af006350 於 2015-12-30 11:40 AM 編輯

K大大~您好~小弟是C語言初學者想請教一個問題
>>輸入兩數字，將兩數間的數字列印到標準輸出裝置，並使每一行列印不超過10字。
試了很多事~笨笨的我還是不了解如果每行步列印超過10個數字>"<


補充內容 (2015-12-30 11:40 AM):
#include <iostream>
int main()
...
瀏覽完整內容，請先 註冊 或 登入會員
若登入不正常或變回訪客狀態，請先刪除COOKIE再登入。

使用道具檢舉

gitlab

帖子
100
積分
93 點
潛水值
9200 米
8樓
發表於 2015-12-30 01:50 PM|只看該作者
如果瀏覽伊莉時速度太慢或無法連接，可以使用其他分流瀏覽伊莉，www01.eyny.com(02,03)。
chevylin0802 自己也分不清c/c++ 依然能大放厥詞，他的話不用太在意

他即使能告訴你10種使用libm的方法，但他也不會知道 libm 的實作就是以牛頓法為基礎，加上許多神奇的優化，例如

1. 先計算 inverse square root 而非直接求 square root
2. 初值用一個magic number，比起從 x/2 開始，可以迭代一次就收斂

數值方法絕對是CS領域的一大瑰寶

低級碼農的特色就是難以超越語言層次，他會告訴你很多看起來很實用但實際上可能會錯誤的用法，例如：不知所云的泰勒展開、寫了macro卻不加括號、用cast取floor…等等。
...
瀏覽完整內容，請先 註冊 或 登入會員
成為伊莉的版主，你將獲得更高級和無限的權限。把你感興趣的版面一步步地發展和豐盛，那種滿足感等著你來嚐嚐喔。

使用道具檢舉

qulzvul3 該用戶已被刪除
9樓
發表於 2016-2-21 06:06 PM|只看該作者
分享使你變得更實在，可以使其他人感到快樂，分享是我們的動力。今天就來分享你的資訊、圖片或檔案吧。
之前要優化開更號的時候看到的某個技術, 可以搜尋
"Quake-III代碼里神奇的浮點開方函數"
其中理論可以由浮點表示法去推導... (跟神奇數字還是有點差異)
可惜, 當時優化的是定點數, 此法無法使用!!
若有安裝色情守門員，可用無界、自由門等軟件瀏覽伊莉。或使用以下網址瀏覽伊莉: http://www.eyny.com:81/index.php

使用道具檢舉

superwaterdog

帖子
309
積分
0 點
潛水值
11174 米
10樓
發表於 2016-3-8 10:03 PM|只看該作者
成為伊莉的版主，你將獲得更高級和無限的權限。把你感興趣的版面一步步地發展和豐盛，那種滿足感等著你來嚐嚐喔。
謝謝分享了
這樓有點蓋歪了

解法有很多
省記憶體 省程序就是好分法




如果你忘記伊莉的密碼，請在登入時按右邊出現的 '找回密碼'。輸入相關資料後送出，系統就會把密碼寄到你的E-Mail。

使用道具檢舉

返回列表發新帖
高級模式
BColorImageLinkQuoteCodeSmilies
您需要登錄後才可以回帖 登錄 | 註冊

Powered by Discuz!

© Comsenz Inc.

重要聲明：本討論區是以即時上載留言的方式運作，對所有留言的真實性、完整性及立場等，不負任何法律責任。而一切留言之言論只代表留言者個人意見，並非本網站之立場，用戶不應信賴內容，並應自行判斷內容之真實性。於有關情形下，用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本討論區受到「即時上載留言」運作方式所規限，故不能完全監察所有留言，若讀者發現有留言出現問題，請聯絡我們。有權刪除任何留言及拒絕任何人士上載留言，同時亦有不刪除留言的權利。切勿上傳和撰寫 侵犯版權(未經授權)、粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論，敬請自律。本網站保留一切法律權利。
回頂部