EDIT: But I can’t find any acknowledgement in either the “Recursive Image Rotation” YouTube video, the original tweet, or the source code.
EDIT2: In a Reddit thread¹, they acknowledge a PDF of a book from 2019². The book itself gives no acknowledgements for the algorithm.
Pages 26 through 28, "The Evolution of Smalltalk: From Smalltalk-72 through Squeak"
Proc. ACM Program. Lang., Vol. 4, No. HOPL, Article 85. Publication date: June 2020.
> The Byte article on “The Smalltalk Graphics Kernel” [Ingalls 1981] details Smalltalk methods that,
with BitBlt at their core, can lay out and display text, draw lines, and magnify and rotate images—each in little more than a dozen lines of code.
> Daniel H. H. Ingalls. 1981. The Smalltalk Graphics Kernel. Byte 6, 8, 168–194. https://archive.org/details/byte-magazine-1981-08/page/n181/...
In that reference, the bitmap rotation is on page 188 in the original publication (page 202 of the archived document).
This seems incorrect. It sounds like you are saying that you can store any 100 random values into 70 values. Or 100 bits of information in to 70 bits.
If you could, what would stop you from then storing that 70 bits in 49 bits, then that 49 in ~34 bits, etc and therefor have infinite information storage?
Each interpolation step causes loss of resolution and the multiple passes might in practice make it slower due to increased memory bandwidth requirements compared to a single pass algorithm.
That of course doesn't take away that it's an interesting trick to know about.
It's Turbo Pascal with inline ASM.
X = 31;
Y = 25;
console.log(X, Y); // prints 31 25
X = X + Y;
Y = X - Y;
X = X - Y;
console.log(X, Y); // prints 25 31
Also, that algorithm has nothing in common with the image rotation one; the image rotation algorithm does require a temporary buffer.
X = 31
Y = 25
X, Y = Y, X
BTW, in Python, "a,b = b,a" is actually faster (execution time) than explicitly using a third variable.
In other words, I am not saying it is a bad technique, just saying it has to use additional resources for the swap, that's all.
In fact, the Python idiom is faster even if you doing something like:
a,b = b[:],a[:]
I would claim it's not semantics. Variables are meant for humans, not computers. Variable does not necessarily mean storage. If you're outside of interpreted languages, the code you type is very often not the code that is executed. If this were a compiled language, there's no way to know if temporary storage was used or not, without looking at the generated machine code. There's a very real chance that something as useless as swapping variables would be optimized away completely.
It doesn’t rotate A, B, C, and D, though. So, we have to rotate the four smaller blocks A, B, C, D.
Let’s assume the algorithm works. Then, we can recurse into each of the smaller blocks.
Eventually, you hit the case where A, B, C, and D are 1×1 pixels (and the image 2×2 pixels). Here, you cannot recurse anymore, but luckily, you notice that you can’t see the difference between a single pixel and that pixel rotated by 90 degrees. So, for sunblocks that small, you don’t have to rotate the pixels. Because of that, the 2×2 case works. Because of that, the 4×4 case works, etc.
You could also say it doesn’t work. If, say, your pixels had a wood grain running horizontally, that grain would still run horizontally after this set of shifts.
The algorithm as presented turns the image into a quadtree as it works, for then re-flattens it. But if we store the image as a quadtree to begin with, we obtain other advantages:
1. We can memoize operations like rotation so that the algorithm goes much faster for images that have large blocks of a single colour or pattern;
2. We can write other operations that recursively apply to the image, like changing one color to another.
A B C D M I E A
E F G H N J F B
I J K L O K G C
M N O P P L H D
D H L P P O N M
C G K O L K J I
B F J N H G F E
A E I M D C B A
Compare to the normal way you rotate things by right angles where e.g. new_image(x,y) = old_image(y, old_height - x), which is extremely embarrassingly parallel.
The actual reason is that it is fun.
If you implement this as a view (rather than imperatively), you can get the compiler to optimize out four successive rotations to nothing :)
But yes, it's mostly fun :)
- moving data in stages like the OP video which might be better for the cache (I don’t believe this) but would require writing to/from me more multiple times per pixel which I think would make it slower
- Accessing memory in a certain order when doing this on a cpu. Certainly that is a reasonable thing to expect to improve performance (roughly breaking the image into blocks that fit exactly into N cache lines, rotating in registers/memory, then writing into exactly N cache lines means you aren’t reading data from RAM/cache that you can’t use), but I don’t think that is related to the recursive process described in the article, unless you mean that you can use this process to get some operations like block(x,y,16) moves to block(s,t,16) and those could be executed cache-efficiently? But then this recursive method is more confusing and more restrictive on the image size than the thing I tried to describe at the start of this bullet point
The degenerate case is when the right quadrangle is already a square with 2^n sides, in which case there is no padding to remove.