writeups
xor_singleheader
| writeups | xor_singleheader | |
|---|---|---|
| 4 | 2 | |
| 49 | 329 | |
| - | 4.0% | |
| 0.0 | 6.1 | |
| about 1 year ago | 3 months ago | |
| Sage | C | |
| - | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
writeups
-
Bitcoin tries to maintain 10 minutes between each block. This gives everyone in the world enough time to update their ledgers. Consistency is difficult when millions of machines are turned on and off every day. And yet, bitcoin is still becoming more reliable by the block
However, averaged over sufficiently long periods of time, the duration of blocks tends to be 600.5958 seconds (10 minutes times 2016/2014, see https://github.com/sipa/writeups/tree/main/bitcoin-difficulty-adjustment for a very mathematical explanation). If the average tends to less than that, it implies the hashrate is on average growing. If the average tends to more than that, it implies the hashrate is average shrinking.
- Private Authentication Protocols
-
An optimal algorithm for bounded random integers
You may be interested in this work going in the opposite direction, holding the bias constant and extracting the most ranges from a constant amount of randomness:
https://github.com/sipa/writeups/tree/main/uniform-range-ext...
This work is interesting because generating random bits via strong generators is typically much more expensive than extraction-- so it can be very useful in cases where a number of small random values are needed in a tight loop such as for some kinds of hash table and generating permutations.
-
A fast alternative to the modulo reduction
I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties.
A write-up is here, in case anyone is interested: https://github.com/sipa/writeups/tree/main/uniform-range-ext...
xor_singleheader
- A fast alternative to the modulo reduction
-
Bloom Filters – Much, much more than a space efficient hashmap
Yes. Some variants of ribbon filters are very fast, and other variants (which are a bit slower thought) need very little space: only a few percent more than the theoretical lower bound.
For static sets, ribbon filters and binary fuse filters (e.g. here: https://github.com/FastFilter/xor_singleheader) are very competitive. Both are based on recent (2019 and newer) theoretical work from Stefan Walzer, e.g. this one https://arxiv.org/pdf/1907.04749.pdf
What are some alternatives?
fastfilter_cpp - Fast Approximate Membership Filters (C++)
awesome-ethereum-rollups - A list of resources related to scaling with rollups.
Golomb-coded-map - A space-efficient, associative alternative to the Bloom filter
fastfilter_java - Fast Approximate Membership Filters (Java)