3 ms·
Depends on what you call brute force. I think what one should call the brute force method is either the approximation by inscribed and circumscribed polygons (h
by Someone 5y ago
Depends on what you call brute force. I think what one should call the brute force method is either the approximation by inscribed and circumscribed polygons (https://www.geogebra.org/m/BhxyBJUZ https://www.geogebra.org/m/BhxyBJUZ) or https://en.wikipedia.org/wiki/Leibniz_formula_for_π https://en.wikipedia.org/wiki/Leibniz_formula_for_π, https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_value_of_π_(pi) https://en.wikipedia.org/wiki/Madhava_of_Sangamagrama#The_va...
The much faster algorithms known today still require lots of force, but I wouldn’t call them brute force.
If the search string is long, it might even be faster to not generate each digit, but use (a variant of) Boyer-Moore to do the search (https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer–Moore_string-search_algo...)
I guess “long” would have to very long for that to be profitable, though.
There also is no known algorithm to do that that is known to terminate (if π is normal, they would, but we don’t know whether it is)