Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

FizzleFade

fabiensanglard.net

Post reply on HN
Print view View original

21–30 of 182 posts

Re: FizzleFade

#21

Post by afpx »

peteretep wrote: post #17
pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

> I have the feeling that knowledge > about bits is lacking by a lot of > younger coders. And I also think > this is what causes bloatware From a management perspective, I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems, and instead turn to "clever" solutions that are costly in terms of extra developer time needed for deve…

It depends on the person, obviously. But, I hope you sprinkle in a few of those types of analysis questions in your standardized interviews so that older people like me even have a chance.

It hurts (both emotionally and financially) to be rejected by younger teams because they assume things about me that aren't true. I now get the dreaded "has too much experience and would be bored" rejection line all too often.

Re: FizzleFade

#22

Post by xorcist »

peteretep wrote: post #17
pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

> I have the feeling that knowledge > about bits is lacking by a lot of > younger coders. And I also think > this is what causes bloatware From a management perspective, I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems, and instead turn to "clever" solutions that are costly in terms of extra developer time needed for deve…

> I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems,

I regularly see the exact opposite: People throwing money and hardware at problems instead of doing the simple and obvious thing. I guess that makes me officially old.

Re: FizzleFade

#23

Post by digi_owl »

keithnz wrote: post #20
pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

there's still the whole other world of coders doing "embedded" software. They are still happily bit fiddling in blissful ignorance of web development fads. I only do a little bit these days, but one of the micros I program only has 20bytes of RAM to work with and requires bit magic. :)

Sadly many these days conflate "embedded" with RPi, Beaglebone or some other SoC on a board...

Re: FizzleFade

#24

Post by eru »

xorcist wrote: post #22
peteretep wrote: post #17

Earlier quoted context omitted.

> I have the feeling that knowledge > about bits is lacking by a lot of > younger coders. And I also think > this is what causes bloatware From a management perspective, I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems, and instead turn to "clever" solutions that are costly in terms of extra developer time needed for deve…

> I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems, I regularly see the exact opposite: People throwing money and hardware at problems instead of doing the simple and obvious thing. I guess that makes me officially old.

You can often see a bit bump in complexity when going from single computer to some kind of cluster environment (be that hadoop or similar). That complexity also often decreases efficiency.

So it can be useful to think a bit to be able to stay on one machine.

But making those trade-offs is exactly what engineering is about, and what's hard. So talking in the very abstract is seldom useful.

Re: FizzleFade

#25

Post by eru »

digi_owl wrote: post #23
keithnz wrote: post #20

Earlier quoted context omitted.

there's still the whole other world of coders doing "embedded" software. They are still happily bit fiddling in blissful ignorance of web development fads. I only do a little bit these days, but one of the micros I program only has 20bytes of RAM to work with and requires bit magic. :)

Sadly many these days conflate "embedded" with RPi, Beaglebone or some other SoC on a board...

Even the chips you find on your credit card have quite a lot of RAM these days, don't they?

Re: FizzleFade

#26

Post by eru »

jstimpfle wrote: post #7

What properties are required in an LFSR that it covers the whole range (2^n-1 numbers) before returning? Or are such configurations found experimentally?

I think some number theory should give you the answer. Look for something about cyclic groups and their generators..

Re: FizzleFade

#27

Post by buzzybee »

FizzleFade is also found in Microprose games from the era (e.g. Railroad Tycoon, Civilization), sometimes in full-screen transitions and other times to fade in single sprites. But more relevantly to "id software history", you can find it in Origin's Space Rogue, which John Romero contributed to. A likely possibility is that he picked up the trick on this or a previous project while at Origin.

It's also possible to use a slower "arbitrary PRNG and bump" scheme that tests the VRAM for the desired values(e.g. if it were a sprite, by running the blit at that pixel address and testing) and walks forwards or backwards until an unset value is found. If the walk can be done fast enough, it'll execute at the same framerate as an LFSR cycle-length fade. It can be further supplemented with an estimation heuristic or a low-resolution map to generate unique patterns. It's just less speedy and mathematically interesting to do that.

Re: FizzleFade

#28

Post by hasenj »

afpx wrote: post #19
pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

Recently, I started helping out data engineering teams improve performance of their big data processing pipelines. Man, was I shocked. Very smart, highly educated, mid-level and even senior software engineers seem to know very little about bits these days. When they'd run into a memory issue, their natural response was to just spin up a few more servers and throw another terabyte of memory at the problem. Makes sense…

It's lucrative for SaaS providers to convince developers that they don't need to care about performance. Just throw more memory at your problem. We'll be there to provide you all the hardware you need. wink wink.

Re: FizzleFade

#29

Post by pfedak »

jstimpfle wrote: post #7

What properties are required in an LFSR that it covers the whole range (2^n-1 numbers) before returning? Or are such configurations found experimentally?

Galois generators of the sort in the article can be described naturally using the finite field Z_2[x]/p(x), that is, polynomials with coefficients taken mod two, where we consider polynomial p(x) is equivalent to zero. If p has degree n, this field has 2^n elements - the 2^n polynomials with degree less than n are distinct, but x^n is equivalent to x^n-p(x), which has degree less than n, so everything with higher degree is already accounted for. This is, however, only actually a field if p is irreducible.

Now we can describe the generator as multiplication by x, where the leftmost bit is the lowest power, since every bit moves right except for the rightmost, which corresponds to turning x^n into x^n-p(x) as above. The cycle length is the smallest k such that x^k is equivalent to 1. Now, an interesting property of finite fields is that there is always a "primitive" element, the powers of which generate every other element (you can prove this inductively by counting elements z such that z^d = 1 for different d, and noting that z^d-1, as a degree d polynomial, has at most d roots in the field). If x is primitive, it will cycle through all other values before reaching 1. In the specific case of n=17, however every element of the field is primitive (this is easy group theory, the nonzero elements form a group under multiplication, and that group has a prime number of elements).

This means any degree-17 polynomial which is irreducible in Z_2[x] will give rise to a full-cycle-length generator. Luckily, finding an irreducible polynomial isn't too hard - of the 2^16 options (ignoring the ones without a constant term, which are obviously divisible by x), 7710 are irreducible by my quick Mathematica computation.

Re: FizzleFade

#30

Post by oblio »

pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

> I have the feeling that knowledge about bits is lacking by a lot of younger coders.

I optimize for what they pay me for now. I also optimize for what I think they will pay me in future.

The super efficient C solution might be an salary dead-end when management also accepts a huge Hadoop solution :)

Post reply on HN