Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit760d9be

Browse files
aryanshbgithub-actionspre-commit-ci[bot]cclauss
authored
Added Fast Inverse Square Root (TheAlgorithms#11054)
* Feat: Added Fast inverse square root* Fix: Added typehint* Fix: Added doctests that break the code, changed var name* updating DIRECTORY.md* [pre-commit.ci] auto fixes from pre-commit.com hooksfor more information, seehttps://pre-commit.ci* Fix: fixed length of docstring* Update fast_inverse_sqrt.py---------Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>Co-authored-by: Christian Clauss <cclauss@me.com>
1 parenteafdb8b commit760d9be

File tree

2 files changed

+64
-0
lines changed

2 files changed

+64
-0
lines changed

‎DIRECTORY.md

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@
3434
*[Bitwise Addition Recursive](bit_manipulation/bitwise_addition_recursive.py)
3535
*[Count 1S Brian Kernighan Method](bit_manipulation/count_1s_brian_kernighan_method.py)
3636
*[Count Number Of One Bits](bit_manipulation/count_number_of_one_bits.py)
37+
*[Excess 3 Code](bit_manipulation/excess_3_code.py)
3738
*[Gray Code Sequence](bit_manipulation/gray_code_sequence.py)
3839
*[Highest Set Bit](bit_manipulation/highest_set_bit.py)
3940
*[Index Of Rightmost Set Bit](bit_manipulation/index_of_rightmost_set_bit.py)
@@ -170,7 +171,10 @@
170171
* Arrays
171172
*[Equilibrium Index In Array](data_structures/arrays/equilibrium_index_in_array.py)
172173
*[Find Triplets With 0 Sum](data_structures/arrays/find_triplets_with_0_sum.py)
174+
*[Index 2D Array In 1D](data_structures/arrays/index_2d_array_in_1d.py)
175+
*[Kth Largest Element](data_structures/arrays/kth_largest_element.py)
173176
*[Median Two Array](data_structures/arrays/median_two_array.py)
177+
*[Monotonic Array](data_structures/arrays/monotonic_array.py)
174178
*[Pairs With Given Sum](data_structures/arrays/pairs_with_given_sum.py)
175179
*[Permutations](data_structures/arrays/permutations.py)
176180
*[Prefix Sum](data_structures/arrays/prefix_sum.py)
@@ -368,6 +372,7 @@
368372
##Electronics
369373
*[Apparent Power](electronics/apparent_power.py)
370374
*[Builtin Voltage](electronics/builtin_voltage.py)
375+
*[Capacitor Equivalence](electronics/capacitor_equivalence.py)
371376
*[Carrier Concentration](electronics/carrier_concentration.py)
372377
*[Charging Capacitor](electronics/charging_capacitor.py)
373378
*[Charging Inductor](electronics/charging_inductor.py)
@@ -531,12 +536,14 @@
531536
##Machine Learning
532537
*[Apriori Algorithm](machine_learning/apriori_algorithm.py)
533538
*[Astar](machine_learning/astar.py)
539+
*[Automatic Differentiation](machine_learning/automatic_differentiation.py)
534540
*[Data Transformations](machine_learning/data_transformations.py)
535541
*[Decision Tree](machine_learning/decision_tree.py)
536542
*[Dimensionality Reduction](machine_learning/dimensionality_reduction.py)
537543
* Forecasting
538544
*[Run](machine_learning/forecasting/run.py)
539545
*[Frequent Pattern Growth](machine_learning/frequent_pattern_growth.py)
546+
*[Gradient Boosting Classifier](machine_learning/gradient_boosting_classifier.py)
540547
*[Gradient Descent](machine_learning/gradient_descent.py)
541548
*[K Means Clust](machine_learning/k_means_clust.py)
542549
*[K Nearest Neighbours](machine_learning/k_nearest_neighbours.py)
@@ -598,6 +605,7 @@
598605
*[Extended Euclidean Algorithm](maths/extended_euclidean_algorithm.py)
599606
*[Factorial](maths/factorial.py)
600607
*[Factors](maths/factors.py)
608+
*[Fast Inverse Sqrt](maths/fast_inverse_sqrt.py)
601609
*[Fermat Little Theorem](maths/fermat_little_theorem.py)
602610
*[Fibonacci](maths/fibonacci.py)
603611
*[Find Max](maths/find_max.py)
@@ -648,6 +656,7 @@
648656
*[Numerical Integration](maths/numerical_analysis/numerical_integration.py)
649657
*[Runge Kutta](maths/numerical_analysis/runge_kutta.py)
650658
*[Runge Kutta Fehlberg 45](maths/numerical_analysis/runge_kutta_fehlberg_45.py)
659+
*[Runge Kutta Gills](maths/numerical_analysis/runge_kutta_gills.py)
651660
*[Secant Method](maths/numerical_analysis/secant_method.py)
652661
*[Simpson Rule](maths/numerical_analysis/simpson_rule.py)
653662
*[Square Root](maths/numerical_analysis/square_root.py)
@@ -814,6 +823,7 @@
814823
*[Ideal Gas Law](physics/ideal_gas_law.py)
815824
*[In Static Equilibrium](physics/in_static_equilibrium.py)
816825
*[Kinetic Energy](physics/kinetic_energy.py)
826+
*[Lens Formulae](physics/lens_formulae.py)
817827
*[Lorentz Transformation Four Vector](physics/lorentz_transformation_four_vector.py)
818828
*[Malus Law](physics/malus_law.py)
819829
*[Mass Energy Equivalence](physics/mass_energy_equivalence.py)

‎maths/fast_inverse_sqrt.py

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
"""
2+
Fast inverse square root (1/sqrt(x)) using the Quake III algorithm.
3+
Reference: https://en.wikipedia.org/wiki/Fast_inverse_square_root
4+
Accuracy: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Accuracy
5+
"""
6+
7+
importstruct
8+
9+
10+
deffast_inverse_sqrt(number:float)->float:
11+
"""
12+
Compute the fast inverse square root of a floating-point number using the famous
13+
Quake III algorithm.
14+
15+
:param float number: Input number for which to calculate the inverse square root.
16+
:return float: The fast inverse square root of the input number.
17+
18+
Example:
19+
>>> fast_inverse_sqrt(10)
20+
0.3156857923527257
21+
>>> fast_inverse_sqrt(4)
22+
0.49915357479239103
23+
>>> fast_inverse_sqrt(4.1)
24+
0.4932849504615651
25+
>>> fast_inverse_sqrt(0)
26+
Traceback (most recent call last):
27+
...
28+
ValueError: Input must be a positive number.
29+
>>> fast_inverse_sqrt(-1)
30+
Traceback (most recent call last):
31+
...
32+
ValueError: Input must be a positive number.
33+
>>> from math import isclose, sqrt
34+
>>> all(isclose(fast_inverse_sqrt(i), 1 / sqrt(i), rel_tol=0.00132)
35+
... for i in range(50, 60))
36+
True
37+
"""
38+
ifnumber<=0:
39+
raiseValueError("Input must be a positive number.")
40+
i=struct.unpack(">i",struct.pack(">f",number))[0]
41+
i=0x5F3759DF- (i>>1)
42+
y=struct.unpack(">f",struct.pack(">i",i))[0]
43+
returny* (1.5-0.5*number*y*y)
44+
45+
46+
if__name__=="__main__":
47+
fromdoctestimporttestmod
48+
49+
testmod()
50+
# https://en.wikipedia.org/wiki/Fast_inverse_square_root#Accuracy
51+
frommathimportsqrt
52+
53+
foriinrange(5,101,5):
54+
print(f"{i:>3}:{(1/sqrt(i))-fast_inverse_sqrt(i):.5f}")

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp