A gyökvonás körülbelül mennyivel memóriaigényesebb művelet, mint egy modulo osztás? (C, [python])
Olyan programot írok, ami kiírja a prímszámokat. Próbálom optimalizálni, és ehhez azt szedtem össze, hogy a megelőző prímszámokat egy tömbben (listában) tárolom, és a vizsgált számot is csak azokkal a prímszámokkal osztom, amelyek <= a szám négyzetgyökével.
Arra lennék kíváncsi, hogy a gyökvonással nyerek-e azzal szemben, mintha elvégezném az összes osztást.
válasza:Nyersz, főleg nagyobb számoknál.
Viszont ki lehet küszöbölni, a változód négyzetre emelésével.
i*i < n
válasza:A gyökvonás a legköltségesebb "elemi" művelet. Newton módszert használ a gyök reciprokának a numerikus közelítésére. Ezért van az, hogy a reciprok gyök rsqrt() például egy osztással gyorsabb mint a sima gyök vonás.
Ahogy az első is mondja a legjobb megoldás (főleg ha csak össze akarod őket hasonlítani), hogyha a másik számot emeled négyzetre.
Tehát a
ref <= sqrt(num)
lasasbb, mint a
ref * ref <= num
Ráadásul mivel tömbbe tárolod, eleve tárolhatod a négyzetét, így csak egyszer kell szoroznod.
válasza:"Viszont ki lehet küszöbölni, a változód négyzetre emelésével."
Milyen jó ötlet :)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!