Mikrocontroller und Digitale Elektronik
›
Thread
AVR: Wurzel von Integer sqrt(uint16)
M
Markus Gast
22.12.2007 15:41 #734218
Hi,
wie kann ich aus einem unsigned int die Wurzel ziehen? Ich finde nur
Routinen für Float.
G
google Gast
22.12.2007 15:54 #734223
Google mal nach "sqrt integer" und du wirst schnell fündig.
RS
Roman Schlager Gast
22.12.2007 18:43 #734309
Stichwort : Schrifliches Wurzelziehen
M
Markus Gast
23.12.2007 09:44 #734538
Ich hab was gefunden das ursprünglich für Long gedacht war. Ich hab es
auf Int gekürzt. Hier das Ergebnis.
1 static const int sqrttable [] = {
2 0 , 16 , 22 , 27 , 32 , 35 , 39 , 42 , 45 , 48 , 50 , 53 , 55 , 57 ,
3 59 , 61 , 64 , 65 , 67 , 69 , 71 , 73 , 75 , 76 , 78 , 80 , 81 , 83 ,
4 84 , 86 , 87 , 89 , 90 , 91 , 93 , 94 , 96 , 97 , 98 , 99 , 101 , 102 ,
5 103 , 104 , 106 , 107 , 108 , 109 , 110 , 112 , 113 , 114 , 115 , 116 , 117 , 118 ,
6 119 , 120 , 121 , 122 , 123 , 124 , 125 , 126 , 128 , 128 , 129 , 130 , 131 , 132 ,
7 133 , 134 , 135 , 136 , 137 , 138 , 139 , 140 , 141 , 142 , 143 , 144 , 144 , 145 ,
8 146 , 147 , 148 , 149 , 150 , 150 , 151 , 152 , 153 , 154 , 155 , 155 , 156 , 157 ,
9 158 , 159 , 160 , 160 , 161 , 162 , 163 , 163 , 164 , 165 , 166 , 167 , 167 , 168 ,
10 169 , 170 , 170 , 171 , 172 , 173 , 173 , 174 , 175 , 176 , 176 , 177 , 178 , 178 ,
11 179 , 180 , 181 , 181 , 182 , 183 , 183 , 184 , 185 , 185 , 186 , 187 , 187 , 188 ,
12 189 , 189 , 190 , 191 , 192 , 192 , 193 , 193 , 194 , 195 , 195 , 196 , 197 , 197 ,
13 198 , 199 , 199 , 200 , 201 , 201 , 202 , 203 , 203 , 204 , 204 , 205 , 206 , 206 ,
14 207 , 208 , 208 , 209 , 209 , 210 , 211 , 211 , 212 , 212 , 213 , 214 , 214 , 215 ,
15 215 , 216 , 217 , 217 , 218 , 218 , 219 , 219 , 220 , 221 , 221 , 222 , 222 , 223 ,
16 224 , 224 , 225 , 225 , 226 , 226 , 227 , 227 , 228 , 229 , 229 , 230 , 230 , 231 ,
17 231 , 232 , 232 , 233 , 234 , 234 , 235 , 235 , 236 , 236 , 237 , 237 , 238 , 238 ,
18 239 , 240 , 240 , 241 , 241 , 242 , 242 , 243 , 243 , 244 , 244 , 245 , 245 , 246 ,
19 246 , 247 , 247 , 248 , 248 , 249 , 249 , 250 , 250 , 251 , 251 , 252 , 252 , 253 ,
20 253 , 254 , 254 , 255
21 };
22
23 static inline unsigned int isqrt ( unsigned int x )
24 {
25 unsigned char xn ;
26
27 if ( x >= 0x100 )
28 {
29 if ( x >= 0x1000 )
30 {
31 if ( x >= 0x4000 )
32 {
33 xn = ( sqrttable [ x >> 8 ] ) + 1 ;
34 }
35 else
36 {
37 xn = ( sqrttable [ x >> 6 ] >> 1 ) + 1 ;
38 }
39 }
40 else
41 {
42 if ( x >= 0x400 )
43 {
44 xn = ( sqrttable [ x >> 4 ] >> 2 ) + 1 ;
45 }
46 else
47 {
48 xn = ( sqrttable [ x >> 2 ] >> 3 ) + 1 ;
49 }
50
51 }
52
53 return (( xn * xn ) > x ) ? -- xn : xn ;
54 }
55 else
56 {
57 if ( x >= 0 )
58 {
59 return sqrttable [ x ] >> 4 ;
60 }
61
62 }
63 }
Hier gibt es meiner Meinung nach sehr schnelle und vor allem kleine
Wurzelfunktionen für 16 und 32bit in Assembler (und noch eine Menge
andere nützliche Ding):
http://elm-chan.org/cc_e.html
M
Markus Gast
23.12.2007 12:59 #734621
Laut Simulator ist meine Version schneller. Die Routine von Chan braucht
mindestens 177 Takte (habe es nicht getestet).
Meine Version braucht laut Simulator 145 Taktzyklen inkl Sprung in die
Routine, Ret und einer Addition +1. Also diese komplette Zeile
Dafür ist sie mit 33 Words aber etwa um den Faktor 10 kleiner als deine.
Entweder schnell oder klein. Beides auf einmal geht leider nur selten.
M
Markus Gast
23.12.2007 13:34 #734647
Das ist klar. Ich brauch halt die Tabelle. Aber es soll ja auch nicht
grad in einen Tiny13 der eh schon knapp voll ist
↑ Nach oben← Zurück zu Mikrocontroller und Digitale Elektronik
Antwort schreiben
Eine eigene Frage?
Dieser Thread ist über 18 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
Neuen Thread starten
Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.
