9 ms·
Why the CORDIC algorithm lives rent-free in my head
- 1oooqooq 3y agoso, it's a https://en.wikipedia.org/wiki/Farey_sequence https://en.wikipedia.org/wiki/Farey_sequence (aka mediant, aka naive fraction sum for approximation) but for angles?
- kevindamm 3y agoMore like a binary search, but instead of adjusting an array index you're iterating an orthonormal matrix which represents rotation about the origin.
- tapatio 3y agoOr a second order step response.
- nico 3y agoThat’s super cool Thank you for that link, very interesting diagrams and structures They look very similar to what a neural network might be in certain cases, and it seems like the structures are trying to map some sort of duality
- ykonstant 3y agoIt is not, because the subdivisions in CORDIC do not possess the best approximation properties of Farey fractions. For that, you would have to partition the circle into major/minor arcs instead, in the sense of Hardy-Littlewood's circle method. But that would be computationally very expensive, whereas this binary subdivision is fast, and is made faster using the shift-add tricks.
- 1oooqooq 3y agoi see. thanks. assumed it was just bit shift tricks implementation. but indeed, no mediant.
- nico 3y agoCool algorithm. Might come in handy soon for running neural networks on less powerful hardware :)
- colibri727 3y ago[flagged]
- KeplerBoy 3y agoNeural networks usually don't use trigonometry or complex numbers.
- deleted 3y ago[deleted]
- nico 3y agoFrom the neural network Wikipedia page: > The signal each neuron outputs is calculated from this number, according to its activation function The activation function is usually a sigmoid, which is also usually defined in terms of trigonometric functions Which neural networks don’t use trigonometric functions or equivalent?
- KeplerBoy 3y agoMost activations functions are based on exponential functions. I don't immediately see how cordic would help you calculate e^(x) unless x is complex valued (which it is usually not).
- adgjlsfhk1 3y agosee section B of https://eprints.soton.ac.uk/267873/1/tcas1_cordic_review.pdf https://eprints.soton.ac.uk/267873/1/tcas1_cordic_review.pdf. Generalized cordic can compute hyperbolic trig functions which gives you exponentials. That said, it's still not useful for ML because it's pretty hard to beat polynomials and tables.
- sunpazed 3y agoI have a few vintage programmable HP calculators that implement CORDIC on their 4-bit CPUs. You can also program them to calculate the Taylor expansion of sin() as another approximate method. If you liked this, it’s worth reading Donald Knuth seminal “The Art of Computer Programming” which explains a number of mathematical algorithms by example.
- deleted 3y ago[deleted]
- aftbit 3y ago> Now, it's fairly obvious that rotating by say 22.75˚ is the same as rotating by 45˚ and then -22.5˚ - i.e. we can break up a rotation into smaller parts, with both positive and negative components. Wouldn't that be rotating by 22.5°? Is this an error in the article or my understanding?
- blowski 3y ago“Lives rent-free in my head” is a horrible cliche. By now, it has the same effect as saying “it’s nice” but uses lots more letters.
- rnmmrnm 3y agoI didn't finish yet but I was thinking he's talking about memorizing the algorithm to calculate sines in your head.
- Der_Einzige 3y ago[flagged]
- __MatrixMan__ 3y agoWhat kind of Marxist keeps their ideas in line by collecting rent from some of them but not others?
- junon 3y agoAnd what does this pedantry solve, exactly? It clearly is something the author thinks often enough about and enjoys talking about. Let people enjoy things.
- wodenokoto 3y agoI never liked that phrase either. So what exactly lives in your head and pays rent?
- sublinear 3y agoKnowledge work
- __MatrixMan__ 3y agoKubernetes, which I would evict if it stopped paying rent.
- pynappo 3y agothe "rent" in the saying is the effort to learn and upkeep a certain piece of knowledge in your head, to the point where you can recall it as needed living rent free generally means that you are able to easily recall a piece of knowledge (and often do, even if you don't want to). something that pays rent might be like an important concept for an upcoming school test, for a class you're not interested in.
- brcmthrowaway 3y agoThis used to be all the rage when folks were into DSP
- tapatio 3y agocos + jsin baby.
- apitman 3y agoWhile the author mentions this is mostly applicable to things like FPGAs, there's also an application in gamedev (or any distributed physics simulation). Floating point calculations are tricky to get deterministic across platforms[0]. One solution is to skip floats entirely and implement a fixed-point physics engine. You'd need something like CORDIC to implement all the trig functionality. I started working on such a thing as a fun side project a few years ago but never finished it. One of these days I hope to get back to it. [0]: https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/ https://randomascii.wordpress.com/2013/07/16/floating-point-...
- nextaccountic 3y agoThe nphysics physics simulation library for gamedev used this approach of using fixed point math whenever cross-platform determinism was wanted, with CORDIC. Nphysics however was deprecated. The newer Rapier library (which is a rewrite of the nphysics) instead relies on the guarantees of IEEE-754 2008 to provide cross-platform determinism, which means that it doesn't work with old platforms, but it is deterministic across modern platforms, including wasm. And yes, you can't rely on the transcedental routines provided by each platform (like sine, cosine, etc), those need to be implemented in a way to work the same everywhere. But, this is possible if avoid running on non-compliant platforms. https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsim/ https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsi... https://rapier.rs/docs/user_guides/rust/determinism/ https://rapier.rs/docs/user_guides/rust/determinism/
- boulos 3y agoThat blog post is now a decade old, but includes an important quote: > The IEEE standard does guarantee some things. It guarantees more than the floating-point-math-is-mystical crowd realizes, but less than some programmers might think. Summarizing the blog post, it highlights a few things though some less clearly than I would like: * x87 was wonky * You need to ensure rounding modes, flush-to-zero, etc. are consistently set * Some older processors don't have FMA * Approximate instructions (mmsqrtps et al.) don't have a consistent spec * Compilers may reassociate expressions For small routines and self-written libraries, it's straightforward, if painful to ensure you avoid all of that. Briefly mentioned in the blog post is IEEE-754 (2008) made the spec more explicit, and effectively assumed the death of x87. It's 2024 now, so you can definitely avoid x87. Similarly, FMA is part of the IEEE-754 2008 spec, and has been built into all modern processors since (Haswell and later on Intel). There are still cross-architecture differences like 8-wide AVX2 vs 4-wide NEON that can trip you up, but if you are writing assembly or intrinsics or just C that inspect with Compiler Explorer or objdump, you can look at the output and say "Yep, that'll be consistent".
- rmorey 3y agoI remember in high school precalc, we learned about the Taylor series, and my teacher told us that it was how trig functions were actually implemented on calculators. Well I looked it up and found that it was actually CORDIC, and went and had some fun implementing it in TI Basic
- rossant 3y agoWell, are there _any_ calculators out there that use Taylor expansions?
- snovv_crash 3y agoI've done some work with fast approximate math libraries,and went down this path. Taylor was a dead-end, but Chebyshev polynomials work great. They have the nice property of having (close to) the minimum maximum (minimax) error over the entire range you are approximating.
- toolslive 3y agowell, from memory (this was > 20y ago) - Taylor gives you polynomial optimized for the evaluation of one point. - naive Newton gives you a polynomial with 0 error in the interpolation points [but the system has a bad condition] - Chebychev gives you a polynomial with minimal error over the interval of choice. So there is no real reason to ever use the Taylor series to approximate a function over an interval. The high school math teachers are lying.
- rmorey 3y agonot lying, probably just mistaken
- djmips 3y agoI thought you might be interested to read how the remarkable Sinclair scientific calculator did it's trig, log etc. It wasn't Cordic but the algorithm has similarities. http://files.righto.com/calculator/sinclair_scientific_simulator.html?m=1 http://files.righto.com/calculator/sinclair_scientific_simul...
- the__alchemist 3y agoSide note for 2023: Some modern MCUs are low cost, but have FPUs. A good example is the STM32G4. So, unlike on an M0 MCU or w/e, you can freely use f32, if you don't want fixed point. And you can get these for ~$1-2 / MCU. That said... The G4 also has a hardware CORDIC peripheral that implements this algo for fixed-point uses. Is this mainly to avoid floating point precision losses? You program it using registers, but aren't implementing CORDIC yourself on the CPU; dedicated hardware inside the IC does it.
- kragen 3y agothe cheapest cortex-m4fs in stock on digi-key, trying to omit duplicates, are the 3-dollar nuvoton m481le8ae https://www.digikey.com/en/products/detail/nuvoton-technology-corporation/M481LE8AE/12337382 https://www.digikey.com/en/products/detail/nuvoton-technolog..., the 3-dollar maxim max32660 https://www.digikey.com/en/products/detail/analog-devices-inc-maxim-integrated/MAX32660GWE-T/8742640 https://www.digikey.com/en/products/detail/analog-devices-in..., and the 5-dollar atmel atsamd51 https://www.digikey.com/en/products/detail/microchip-technology/ATSAMD51G18A-MU/7390367 https://www.digikey.com/en/products/detail/microchip-technol.... their cheapest stm32g4 is the stm32g441kbt6 which rounds to 4 dollars https://www.digikey.com/en/products/detail/microchip-technology/ATSAMD51G18A-MU/7390367 https://www.digikey.com/en/products/detail/microchip-technol... where do you get them for under 2 dollars? (digi-key does list the nuvoton chip for barely under 2 dollars in quantity 500)
- the__alchemist 3y agohttps://jlcpcb.com/partdetail/Stmicroelectronics-STM32G431CBU6/C529356 https://jlcpcb.com/partdetail/Stmicroelectronics-STM32G431CB... JLC: $2.1 for qty=1. $1.3 at 1k qty. Loads of stock. It's a low flash and low RAM variant, but sufficient for some purposes. 170Mhz CPU with many onboard periphs.
- kragen 3y agofantastic, thanks!
- 3y ago
- teleforce 3y agoFun facts, in addition to sine and cosine calculation and generation, CORDIC can also be used for many operations including log, exponent, square root, vector magnitude, polar-cartesian conversion and vector rotation. Spoiler alerts, the authors provided the teaser regarding these propects in the conclusions. I've got the feeling that by using quaternion instead of conventional orthonormal matrices, CORDIC based operations can be executed more efficiently (less compute cycles and memory) and effectively (less errors) [1]. [1] CORDIC Framework for Quaternion-based Joint Angle Computation to Classify Arm Movements: https://core.ac.uk/works/8439118 https://core.ac.uk/works/8439118
- nimish 3y agoIt can be extended to arbitrary Lie groups IIRC
- pintor-viejo 3y agoMeagher's octree system notably used only integer arithmetic with no integer multiplication/division: > Efficient (linear time) algorithms have been developed for the Boolean operations (union, intersection and difference), geometric operations (translation, scaling and rotation), N-dimensional interference detection, and display from any point in space with hidden surfaces removed. The algorithms require neither floating-point operations, integer multiplications, nor integer divisions. https://doi.org/10.1016/0146-664X(82)90104-6 https://doi.org/10.1016/0146-664X(82)90104-6 This facilitated creation of fast, custom VLSI graphics acceleration hardware for octree representation.
- kazinator 3y agoIf, having it in your head, you could use it to calculate trig functions in your head, that would be a way of it paying rent. So, yeah.
- larsrc 3y agoSome related articles with hardware implementations: https://arxiv.org/pdf/2211.04053 https://arxiv.org/pdf/2211.04053 https://hal.science/hal-01327460/document https://hal.science/hal-01327460/document https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstracts/1150_Johnson_A.pdf https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstrac... I would love to see how it compares to regular software and hardware trigonometric implementations on various kinds of hardware through the ages.
- teleforce 3y agoThanks for the links. It is a very strange that for a very pervasive and hugely popular computer techniques, CORDIC do not get a proper detailed treatment and coverage in books. Since IoT and machine-to-machine communication are taking off, and with the efficiency of CORDIC implementation and operation, it usages will most probably increase exponentially, hence good references are needed for correct and optimized implementation. The two anomalies are books by Prof. Omondi, and Prof. Deschamps [1],[2]. [1]Computer-Hardware Evaluation of Mathematical Functions: https://www.worldscientific.com/worldscibooks/10.1142/p1054 https://www.worldscientific.com/worldscibooks/10.1142/p1054 [2]Guide to FPGA Implementation of Arithmetic Functions: http://www.arithmetic-circuits.org/guide2fpga/vhdl_codes.htm http://www.arithmetic-circuits.org/guide2fpga/vhdl_codes.htm
- azubinski 3y agoMost important keywords are: BLDC + motor control + sensorless CORDIC is a de facto standard algorithm in the relevant application area. Infineon explains algorithms compactly and clearly: https://www.infineon.com/dgdl/AP1610510_CORDIC_Algorithm.pdf https://www.infineon.com/dgdl/AP1610510_CORDIC_Algorithm.pdf Microchip gives an idea of where and what the algorithm is used for: https://ww1.microchip.com/downloads/aemDocuments/documents/OTH/ApplicationNotes/ApplicationNotes/01078B.pdf https://ww1.microchip.com/downloads/aemDocuments/documents/O... CORDIC hardware accelerators are found in many microcontrollers designed to control electric motors.
- femto 3y agosin and cos are often used to rotate vectors. In these cases, a trick with a CORDIC is to avoid the traditional sin/cos/multiply calculation by using the vector to be rotated as the input to the CORDIC. The CORDIC will directly produce the rotated vector, without having to compute sin/cos or do a complex multiplication. CORDIC really shines when latency doesn't matter so much. You can pipeline every stage of the computation and get a huge throughput. It's well suited for digital mixing in radio systems.
- srean 3y agoI got reminded of a rather cute snippet of code I had a part in. One needed to find the coordinates of the bisector of an angle subtended by an arc of a unit circle. They (x,y) coordinates of the 'arms' were available. The existing implementation was a mass of trigonometry - going from the x,y coordinates to polar (r,θ), then making sure that the θ computed was in the correct quadrant, halving the θ and converting back to x,y coordinates. All in all, many calls to trigonometric functions and inverse functions. This was in Python and thus we had first class access to complex numbers. So all that was needed was to define two complex numbers. z1 from (x1,y1) z2 from (x2,y2) and then take the geometric mean of the product: √(z1*z2). Done. No explicit trigonometry and no explicit conversion and back in the new code.
- pintor-viejo 3y agoThe first place I personally saw CORDIC mentioned was: "How Many Ways Can You Draw a Circle?", the first *Jim Blinn's Corner* article: https://ieeexplore.ieee.org/document/4057251 https://ieeexplore.ieee.org/document/4057251 He found 15 ways, which generalized to methods like CORDIC, etc. A couple years ago I was wondering if SDF shape representation could use something like a taxi cab distance metric to move floating point operations to integer, although I haven't spent too much time investigating it.
- mchinen 3y agoNice to read this. Curious how CORDIC performs against cubic or other polynomial interpolation with a small table. I was taught that resource constrained synthesizers sometimes used cubic interpolation, and this was presumably when CORDIC was relatively new. At a glance, the single bit of precision you get with each iteration of CORDIC means it would be more expensive in compute but cheaper in space than a polynomial. But on the space note I feel we should highlight that it can be cheaper than the article might suggest with the 4096 entry lookup tables for sin(x) - Only a quarter of the full circle is needed due to symmetry.
- Sharlin 3y agoBack in the day gamedevs (and demosceners) used a merely 256-entry LUT for sin and cos – it was convenient to have byte-sized angles that auto-wraparound, and for rotation in 2D games, 2^8 was quite enough. Wouldn’t get you very far in 3D though if you want smooth motion.
- Waterluvian 3y agoI think the love for this algorithm feels similar to my love for Raycasting. You get a 3D game on barely any hardware with no trigonometry. Like… how?! It makes complete sense once I implemented it, but it still feels like wizardry.
- djmips 3y agoI took a stab at a Cordic ATAN2 function in 6502 years ago. This was the first pass. I meant to go back and write a faster version. https://forums.atariage.com/blogs/entry/3385-atan2-in-6502/ https://forums.atariage.com/blogs/entry/3385-atan2-in-6502/