this post was submitted on 01 Apr 2025
184 points (99.5% liked)

Technology

68245 readers
6668 users here now

This is a most excellent place for technology news and articles.

Our Rules

  1. Follow the lemmy.world rules.
  2. Only tech related news or articles.
  3. Be excellent to each other!
  4. Mod approved content bots can post up to 10 articles per day.
  5. Threads asking for personal tech support may be deleted.
  6. Politics threads may be removed.
  7. No memes allowed as posts, OK to post as comments.
  8. Only approved bots from the list below, this includes using AI responses and summaries. To ask if your bot can be added please contact a mod.
  9. Check for duplicates before posting, duplicates may be removed
  10. Accounts 7 days and younger will have their posts automatically removed.

Approved Bots

founded 2 years ago
MODERATORS
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
184
Implementing a spellchecker on 64 kB of RAM back in the 1970s led to a compression algorithm that's technically unbeaten and part of it is still in use today (www.pcgamer.com)
submitted 3 days ago by [email protected] to c/[email protected]
34 comments fedilink hide all child comments
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 16 points 2 days ago (2 children)

I am still in awe of the fast inverse square root method used in QuakeIII. Good times.

[–] [email protected] 5 points 2 days ago

IIRC, someone got with the author of that bit of code to ask how they came up with it, but they had simply learned it from someone else. So they tracked them down and found that they had also learned it from someone else. They eventually landed on Greg Walsh as the original author, but for a bit the code had no known origin.

[–] [email protected] 3 points 2 days ago (1 children)

I read this article and I know it's written in English, but I've accepted defeat in trying to understand it.

I write code for a living and I'm doing my best to ignore the feelings of inadequacy I'm currently experiencing.

[–] [email protected] 4 points 2 days ago* (last edited 2 days ago)

but I’ve accepted defeat in trying to understand it

I may have shared the link but even I don't know how it how it works.

It's like admiring the Eiffel Tower; you can understand that it's a marvel of engineering without understanding the underlying engineering concepts. Such experiences are rare but they truly humble you.

Regarding the square root, understand the following concepts

  1. Bit shifting simply shift the bits to a certain side (Left or right) => 0010 << 1 → 0100
  2. Mathematically, it multiplies or divides the input number with a factor of 2, depending upon the type of shift
  3. If you shift the number n with a nice shift amount x (I have greatly greatly over-simplified this), then you can calculate the inverse sq. root since inverse square root is 2^(-1/2)
  4. Calculating the inverse square root manually will take lots of clock cycles, which was not feasible for a FPS game with the limited h/w
  5. Bit shifting is a lot faster since we are not computing, but instead shifting

The resultant shifting gives us an answer which is close enough to the answer, and that is good enough for FPS games for calculation of reflections.

Source for bitshifting

PS: Someone who is more experienced in this domain can correct me if I'm wrong.