<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Charles Rosenbauer on Medium]]></title>
        <description><![CDATA[Stories by Charles Rosenbauer on Medium]]></description>
        <link>https://medium.com/@bzogrammer?source=rss-7150ebf94b8f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*BwKjZMZEGJb5rKHT.jpg</url>
            <title>Stories by Charles Rosenbauer on Medium</title>
            <link>https://medium.com/@bzogrammer?source=rss-7150ebf94b8f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 19:10:17 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@bzogrammer/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Funding Open Source by Ransom]]></title>
            <link>https://medium.com/@bzogrammer/funding-open-source-by-ransom-21978d84d5aa?source=rss-7150ebf94b8f------2</link>
            <guid isPermaLink="false">https://medium.com/p/21978d84d5aa</guid>
            <category><![CDATA[economics]]></category>
            <category><![CDATA[open-source]]></category>
            <category><![CDATA[funding]]></category>
            <category><![CDATA[ransom]]></category>
            <dc:creator><![CDATA[Charles Rosenbauer]]></dc:creator>
            <pubDate>Wed, 02 Sep 2020 14:01:02 GMT</pubDate>
            <atom:updated>2020-09-02T14:01:02.768Z</atom:updated>
            <content:encoded><![CDATA[<h4>Selling a Single Copy for Public Use</h4><p>I recently wrote an <a href="https://medium.com/@bzogrammer/fixing-software-economics-171875433571">article on the economic problems in open source</a>. This is a subject I could just about write a whole book about, so fitting it into a single article required leaving a lot out.</p><p>To summarize it, most software (especially open source) has the properties of what economists refer to as a <em>public good</em>. Public goods do not play nicely with traditional economics, and are thus very hard to properly fund. This creates a large misallocation of resources, where many important projects don’t receive the funding they require. With how critical this digital infrastructure is getting, it is extremely important that we begin exploring new funding models.</p><p>I will be following it up with a series of articles and podcasts, which for now you can keep up with by following <a href="https://twitter.com/BadgerLabs">Badger Labs</a> on Twitter. I’d like to go into much more detail on some of those ideas, and I’ll start by discussing some options for funding models.</p><h4>Ransoms?</h4><p>The first model I’d like to discuss is a “Ransom Model”. Using this for funding “public goods” was, to my knowledge, first proposed by <a href="https://youtu.be/8TwNNgiNZ7Y?t=4895">Vitalik Buterin</a> of Ethereum fame.</p><p>While perhaps ransoms have a bad connotation, there are many reasons why funding public goods this way makes a lot of sense. The model works like this:</p><p>First, you create the good, and publish some kind of preview online. In the case of software, this could for example be a video demo. It could of course be applied to many other digital goods as well; Vitalik originally developed this approach for funding articles, which would be previewed by publishing the first paragraph. Then, the good is placed up for ransom; if the community can collectively raise enough money to reach a particular goal, it is released to the public and everyone can then access it for free.</p><p>Unlike a traditional ransom, nothing is being stolen, or extorted. The only thing this has in common with the crime is the funding model; I have X, and I’ll release it to the public for $Y.</p><p>In a sense, rather than each individual paying for their own access to it, the public is collectively paying for it in one large purchase, and buying the right for public access. This is a clever way to get around many problems that public goods pose as,especially in the case of digital goods, any control over their distribution is lost as soon as they are released to the public.</p><p>There is also the fact that the costs for public goods is often fixed; once the code is written, creating a billion copies of a program really isn’t much more expensive than just creating one, so why pay for each copy individually when you can just cover the initial cost of development?</p><p>Software maintenance is perhaps a continual cost worth considering, though with improvements in formal verification technology, this will likely diminish over time. Even without this concern, each new update to the software could be seen as a new project that can be funded via a new ransom.</p><h4>Comparison to Crowdfunding</h4><p>This may sound similar to crowdfunding, though it is distinctly different in several ways from the typical kickstarter campaign.</p><p>For one, it shifts risk from the consumers onto the producer; the good is already finished when the ransom is announced, and there is less need to worry that any money you put toward it is being wasted on a product that will never be finished. There is perhaps a concern that the ransom may never be fully raised, however.</p><p>Another big difference is that the funding goal is fixed; while a particularly successful crowdfunding campaign may raise several times its intended goal, a ransom-funded project is capped at a limited price, and the public doesn’t risk overpaying for it.</p><p>This isn’t a strictly<em> better</em> funding model, but just different.</p><p>For example, say you have some open source software you’ve built and are about to release, and want to fund it with a ransom. A ransom shifts a lot more risk onto you; you have to build the software first, and then hope that people see enough value in it to fund it. If you can’t make back your full investment, you take the loss rather than the public.</p><p>This particular property may incentivize developers to fund a variety of smaller projects this way, and use profits from successful ones to cover the losses of unsuccessful ones.</p><h4>Variations</h4><p>The ransom model also has a lot of room for variation.</p><p>For example, what happens if the ransom is never fully paid? Does the ransom eventually expire? If it does, do donors get refunded? Or does the good simply get released after the expiration date, regardless of how much was raised? This second option may be preferable, as no one faces a total loss in the event that funding is unsuccessful. The producer makes back at least part of their investment, and the donors eventually get what they paid for. However, it may also reduce the incentive for the public to fund it as they would then have the option to not pay at all if they’re simply patient enough.</p><p>If the project doesn’t appear to be on track to reach its goal before the ransom expires, what reason does someone have to donate rather than just wait? Perhaps if a project raises only half of its goal, it expires in half the time? A mechanism similar to this would mean that there is never a time where donating <em>something</em> doesn’t result in the project being released sooner.</p><p>What about after the project has been released? If people are enthusiastic about the project, should they have the option to continually donate, at least just to show appreciation? If we have two projects with identical funding goals; one is wildly popular and the other just barely raises its goal, should the developer of the more popular project get a little extra reward?</p><h4>Testing Ransoms</h4><p>Ransoms have a lot of very interesting properties and offer plenty of room for exploration and variation. I encourage anyone working in open source to consider them as an option.</p><p>Stay tuned for the next article, which will discuss the “Pay-It-Forward” model.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=21978d84d5aa" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Fixing Software Economics]]></title>
            <link>https://medium.com/@bzogrammer/fixing-software-economics-171875433571?source=rss-7150ebf94b8f------2</link>
            <guid isPermaLink="false">https://medium.com/p/171875433571</guid>
            <category><![CDATA[digital-public-goods]]></category>
            <category><![CDATA[open-source-software]]></category>
            <category><![CDATA[economics]]></category>
            <category><![CDATA[software]]></category>
            <dc:creator><![CDATA[Charles Rosenbauer]]></dc:creator>
            <pubDate>Tue, 18 Aug 2020 14:01:02 GMT</pubDate>
            <atom:updated>2020-08-18T14:01:02.396Z</atom:updated>
            <content:encoded><![CDATA[<h4>Sustainably Producing Public Goods</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/574/1*Hic8JFgfbR0MHTekw8QAYw.png" /></figure><p>In economics, there is the concept of a public good; a product or service that is non-excludable and non-rivalrous. Non-excludable means that it is impractical to prevent people who do not pay for it from directly benefiting from it, and non-rivalrous means that one person using it does not diminish the ability for someone else to use it simultaneously.</p><p>These two properties together break many of the mechanisms that markets use to produce goods efficiently. If we cannot prevent access by those who do not pay for goods, we cannot prevent free-riders, and thus there is little incentive for anyone to pay despite the fact that everyone benefits.</p><p>Traditionally, economists have seen public goods as an uncommon edge case, that can usually be addressed with funding from governments and nonprofits, albeit with some drawbacks. IP and Patent law also serve as solutions to this problem when a centralized funding approach is less than ideal, though with a different set of advantages and disadvantages.</p><p>The classical example of a public good is an idea; it may require a lot of effort to create a good idea, but once it exists controlling its spread can be very hard. Ideally, we want good ideas to spread as much as possible, as they create more valuable the more people have access to them. On the other hand, the difficulty of controlling them means that it’s hard to compensate those who create these ideas for the effort it took to create them.</p><p>Today we have software. Software is, in a sense, just an idea. Perhaps “pattern” is a more apt term though. Simple patterns can be propagated via language, though there is a limit on how useful they can be. More complex problems often require more complex solutions, which require more complex patterns. Complex patterns can be propagated via language as well, but they are much more cumbersome and inconvenient due to their size. Writing made this much easier, though mass production of books wasn’t feasible until the mid 1400s.</p><p>Mass production of patterns creates opportunities for piracy, threatening the sustainability of pattern production. Luckily, physical media like books have the nice advantage that, with the addition of a mechanism like copyright law, production and distribution can be mostly controlled. Software started out on physical media, but aside from very large programs like videogames that are often still easier to transport via disks and cartridges (though increasingly less and less so), this is no longer the case.</p><p>Now, piracy isn’t completely bad; zero cost means that a pattern can be more widely distributed. There’s a very good reason why copyright law was designed to eventually expire and push ideas into the “public domain.” Regardless, we still need to properly compensate the original creator of the pattern.</p><p>In the case of software, this is especially true. Software may have bugs and security holes, and it is very important to make sure that the digital tools we use work properly. If we don’t compensate people for their work, we are limiting ourselves to low-quality, under-maintained software.</p><p>These concerns are not new.</p><p>Gamers have complained for years that the ability to continually update games created by the move away from physical media has resulted in buggier games.</p><p>In 2014, the Heartbleed bug in OpenSSL created a massive security vulnerability in one of the most widely used and critical pieces of infrastructure on the internet, and cost at least $500M to fix on short notice. This could have been avoided had OpenSSL been maintained by more than just a couple hobbyist developers receiving only $2,000 per year in donations.</p><p>As of the time of writing this, Mozilla, one of the largest companies focused primarily on open source, has just announced it is cutting 25% of its staff, causing many in the open source community to worry that this style of development is getting less and less feasible.</p><p>The software industry is moving into economic territory that we have little experience with, and few ideas on how to make work properly.</p><h4>Finding Solutions</h4><p>Solving this problem is tricky.</p><p>For example, the first solution many jump to is of course donations. Patreon! Github Sponsors! Bitcoin addresses in the README!</p><p>Let’s quick run some numbers though. Suppose we have a perfect, or at least <a href="https://vriad.com/essays/a-new-funding-model-for-open-source-software">pretty good donation system</a>. One that makes it extremely convenient to throw money at all the projects you like. How much money would you expect the average programmer to donate?</p><p>Let’s say that figure is $1000/year. If we consider a standard wage for a full-time developer to be $100,000/year, then for every full-time open source developer, we’d need an average of 100 developers donating. This limits us to no more than 1% of all developers working full-time in open source. If people become extremely generous and donate a very large fraction of their income, or if we can talk most open source developers into working for far less than they could make elsewhere, we could bring that number up. Neither solution is really ideal, so we need a different solution.</p><p>One of the problems with donations is that it’s very easy to ignore them. If a payment isn’t strictly necessary, why put yourself through extra effort to spend a few extra dollars? Once you can get people to open their wallets however, it generally gets much easier to get them to be generous.</p><p>Compare Patreon to Bandcamp; it’s not uncommon for a youtuber with hundreds of thousands of subscribers to have only a couple hundred patrons on Patreon. Fans have to go out of their way if they actually want to support the youtube channel. On the other hand, Bandcamp provides musicians with a Pay-What-You-Want model that allows buyers to choose how much they pay, with a minimum set by the musicians. Bandcamp reports that more than half of purchases are above the minimum price. If someone already has their wallet out, it’s much easier to convince them to spend a little extra.</p><p>Another important thing to question is what exactly we want to monetize. Should projects get some fixed amount each month? Should funding be based on purchases of the software? Should it be based on a cut of profits made by those who use it? Should it be based on grants from governments, nonprofits, or the companies that stand to benefit from it? Should maintenance/updates be held for crowdfunded bounties/ransoms? These are all different ways to fund software, and they result in very different distributions of funding with different priorities.</p><p>We can go deeper. Should funds be distributed to just the regular developers, or to everyone who commits code? How should the value of each commit be calculated? Should small projects band together into funding pools to more evenly distribute funds? Should we do the same thing with software where it may be unclear to someone unfamiliar with technical details which projects deserve the most funding and when? How will improvements in formal verification, etc. change the maintenance requirements of software? Should software that’s sold on a per-unit basis include a “pay-it-forward” approach where users can pay into a pool to help those unable to pay for the software to get it for free?</p><p>A popularity-focused model might not be perfectly ideal. Look at command-line tools like grep. They’re very popular, but they don’t need much in terms of maintenance. If we chose to throw funding at them, it could be argued that those funds would be better invested elsewhere. There is the point that people who produce very valuable things should be rewarded well, as they’ve proven themselves capable of producing valuable things, and we’d prefer if they had plenty of resources to invest in other projects. At the same time, there’s a point (even if it’s very hard to pinpoint where exactly it is) where that money would be better spent elsewhere. Some people also just get really lucky.</p><p>I don’t think we can really expect a perfect solution, but a variety of solutions for different niches and situations is something that we should pursue. That’s the approach we take with software licenses; MIT, BSD, Apache, GPL2, GPL3, LGPL, WTFPL, and the rest all exist for good reasons. Perhaps future software distribution platforms may have a wide variety of templates for funding models in the same way we do licenses today.</p><p>Now is the time to have serious conversations about this, and more importantly to start building solutions.</p><h4>The Consequence of Failing</h4><p>I think the consequences of failing at this perhaps go beyond what most people would expect.</p><p>Where the money is in software development is directly drives what’s feasible and infeasible to build. Money is a feedback mechanism that tells people “do more of this!”. In theory this incentivizes progress, but sometimes a misalignment of incentives drives people elsewhere, and it’s our responsibility to realign these incentives the best we can in the most stable and sustainable way we can.</p><p>If you have a company building software, one solution to the funding problem is to run everything on your own servers. Sell services, not applications. This has many money-making advantages. You can charge a toll for usage, and can simply not provide the service to those who do not pay. You can justify that toll by pointing to your big, expensive servers. You can track everything everyone does and sell their personal information. You’ll make even more money doing that if you’re willing to sell that data to some really shady organizations. It may be unethical, but it lets you wipe out a lot of competition by giving away your service for “free”. You can go further and build network effects and addiction-inducing designs into everything to make it even harder for others to compete. When people complain, it’s a lot easier to lie about what your software does if it’s hiding on a private server that the public can’t independently audit.</p><p>I hope it’s not too controversial that this isn’t exactly an optimal solution. There are cases where a centralized service may be the best option, but we should be sure to judge whether the benefits really outweigh the costs, or if a better solution is possible.</p><p>Another recent example; there are those complaining about Apple taking a 30% cut of all transactions through their app store. Similar complaints have been targeted at a variety of other platforms too. BitTorrent and IPFS show us that centralized servers aren’t necessary for file hosting and sharing. It should certainly be possible to build a purely peer-to-peer online store that allows people to buy and sell digital goods without a middle man (aside from perhaps the payment processor, assuming they aren’t using a cryptocurrency). Of course, the market doesn’t currently incentivize this strongly; after all, while this would be very valuable to many people, where’s the incentive for those who build it?</p><p>Peer-to-Peer applications might not be ideal for every situation, but there are many cases where they have many advantages over the highly centralized services we currently see a lot of. Even in the cases where they introduce difficulties, they may still be at least worth investigating. Tracking the exact numbers of likes/dislikes/retweets/views/etc., on content might make social media harder to build, but it also might just incentivize us to build less quantitative social media platforms. Worst case scenario, it’s at least more options and competition for better software.</p><p>Then there’s the problem of software development tooling. This could be a whole, lengthy series of articles on its own.</p><p>This may be a controversial opinion, but I think that software development tooling — compilers, debuggers, IDEs, etc., have barely improved since the 1980s, if not earlier. You could perhaps even argue that there are <a href="https://www.youtube.com/watch?v=yJDv-zdhzMY">very few widespread ideas newer than 1968</a>.</p><p>While a full argument would probably be best for another time, I will make one point; Abstract Interpretation. <a href="https://www.youtube.com/watch?v=EVkHgKCqAcI">Abstract Interpreters</a>, for those unfamiliar, are tools designed to form sound approximations of undecideable problems. They are extremely powerful tools for automated detection of bugs in software, among many other things. Think of them like a debugger on steroids, though perhaps that’s not even giving them enough credit.</p><p>While used to a very limited extent for compiler optimization, they mostly have not left academia save for the occasional company that will sell you one for an arm and a leg and then some. They’re mostly used by companies writing software for cars, planes, medical devices, and other industries where bugs can easily cost lives. This is technology that could certainly find its way into a standard software developer’s toolkit, and would be extremely valuable. However, this is non-trivial software, and bugs in it can be costly (if there are bugs in the program telling you whether or not your program has bugs, what do you do?).</p><p>The problem is that developer tools, especially the most important tools like compilers, are almost always free. After all, if you build a programming language and try to charge money for it, many people will unwilling or unable to pay for it. Arguably the biggest factor that makes a language valuable isn’t the language itself, but the ecosystem around it. When you rely on the community around it to build such an ecosystem, any barrier to entry, especially a financial one, can seriously hinder any path to growth.</p><p>Simply put: free languages outcompete non-free languages.</p><p>If it were easier to actually build a business around building programming languages, I think there’d be far more innovation going on. Instead, we’re left with languages, IDEs, and debuggers that haven’t changed meaningfully in decades despite very promising work in academia. New approaches are needed.</p><h4>Let’s Start Building</h4><p>Rather than just speak about this, I’m putting effort in myself, and I encourage others to do the same.</p><p>Badger Labs, the startup <a href="https://twitter.com/bzogrammer">I</a> run with <a href="https://twitter.com/Willwaukee">Will Pangman</a>, is working on peer-to-peer software and experimental development tools. While we’re not quite ready to release anything quite yet, we are currently developing a very experimental new programming language, among other things. We plan to try out new funding models for our projects.</p><p>We also are working on releasing articles and podcasts, some of which will be free, and others will mostly serve to experiment with a variety of new funding models. Though the exact subjects will vary, many will be focused on discussing these problems in more detail. There is an awful lot I had to leave out of this article.</p><p>You can follow us and reach out at <a href="http://twitter.com/BadgerLabs">@BadgerLabs</a> on Twitter if any of this sounds interesting to you. If you have any feedback, or ideas, or just want to have a conversation about software economics, please reach out!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=171875433571" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Case for Meme Research]]></title>
            <link>https://medium.com/@bzogrammer/the-case-for-meme-research-d92ec2baf55c?source=rss-7150ebf94b8f------2</link>
            <guid isPermaLink="false">https://medium.com/p/d92ec2baf55c</guid>
            <category><![CDATA[memes]]></category>
            <category><![CDATA[social-media]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[call-to-action]]></category>
            <category><![CDATA[psychology]]></category>
            <dc:creator><![CDATA[Charles Rosenbauer]]></dc:creator>
            <pubDate>Mon, 13 May 2019 21:53:11 GMT</pubDate>
            <atom:updated>2019-05-13T21:53:11.663Z</atom:updated>
            <content:encoded><![CDATA[<p>We need to fund research on internet memes. Yes, I’m entirely serious about this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*S6YJpKPFps0-NxVkpVn9Mw.jpeg" /><figcaption>Pepe is ready to study memes, are you?</figcaption></figure><p>Why do certain memes get popular and others don’t? How do memes spread? Are “weaponized memes” really a thing, and if so, how do we protect ourselves from them?</p><p>I think these are all very good questions, and right now there doesn’t seem to be very much research at all going into answering them. Why not?</p><p>In our modern age, social media has become a massive influence on society. Ideas spread rapidly and can in only a few hours influence millions of minds. Memes are being used to drive political campaigns (like <em>Make America Great Again</em>), and undoubtedly have a great impact on public opinion. So why are we not trying to better understand how this process works?</p><p>Research into this may help us better understand how to make information spread, as well as how to fight back against the spread of bad ideas. If a malicious person or organization starts spreading bad ideas in their memes to influence people, how do we fight back?</p><p>Clearly, more concise information spreads best (which is more likely to spread, a simple slogan, or a nuanced argument?), and information also changes as it spreads and becomes distorted through a big game of telephone. If we understand this process better, we may gain the ability to package our ideas in ways that they not only spread well, but maintain their original meaning for longer.</p><p>Understanding how our brains influence this process may also be interesting. Perhaps we could even narrow down on what calculations our brains are doing by looking at what ideas stay the same and which change as memes spread, and compare and contrast them with a variety of mathematical models of intelligence.</p><p>For example, <a href="https://www.youtube.com/watch?v=YFL-MI5xzgg">researchers recently discovered</a> that neural networks pay more attention to textures than shapes during image recognition, while humans do the opposite; a picture of elephant skin in the shape of a cat will appear as a cat to a human and an elephant to an AI. What can we learn from understanding how humans and AI differ on understanding more complex ideas? Could this not only let us peer into our own minds, but also the minds of the AIs now running the world?</p><p>And speaking of that, clearly which ideas spread on social media affects how memes spread. Right now that’s mostly managed with algorithms and AI. How does the way the AIs interpret our ideas affect which ideas spread?</p><p>So this is a call to action. We need to build a journal for meme research, and we need to pursue and fund meme research. Better understanding the nature of how ideas spread could provide us with great tools for understanding how to cope with the digital age, and deeper insight into ourselves.</p><p>Or at the very least, we may learn how to make even more dank memes.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d92ec2baf55c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Programming in Hyperspace [pt. 2]]]></title>
            <link>https://medium.com/@bzogrammer/programming-in-hyperspace-pt-2-7f62dd568373?source=rss-7150ebf94b8f------2</link>
            <guid isPermaLink="false">https://medium.com/p/7f62dd568373</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[Charles Rosenbauer]]></dc:creator>
            <pubDate>Fri, 12 Apr 2019 19:56:06 GMT</pubDate>
            <atom:updated>2019-04-12T19:56:06.940Z</atom:updated>
            <content:encoded><![CDATA[<p>Okay, in <a href="https://medium.com/@bzogrammer/programming-in-hyperspace-pt-1-726e5d416ba0">part 1</a> I went over some strange applications of bitwise operations; mostly some unique number theory stuff for dealing with repetitive bit patterns, doing horizontal adds, and doing some strange, more obscure operations.</p><p>This time, we’re going even deeper down this rabbit hole, but this time with a special focus on some properties of Bloom Filter -like data structures. Some of the stuff in this article is even used in production, so you’ll probably find some more practically useful things here compared to last time.</p><h3>Review of Bloom Filters</h3><p>Let’s just quick review bloom filters here, as a lot of the rest of this article is built upon strange variations of them.</p><p>A bloom filter is a type of probabilistic data structure. It acts like a set with a lookup operation that guarantees no false negatives, but sometimes provides false positives.</p><p>In other words, it has a lookup operation that answers either “definitely no” or “maybe yes”.</p><p>Bloom filters are also quite fast, and have a fixed storage size; a bloom filter containing one item might take up just as much space as one containing a million. This of course comes with a trade-off; the more data you try to pack into a small amount of space, the less precise it gets and the higher the probability of a false positive. There is a trade-off between accuracy and size, and the exact parameters you need can be easily tuned.</p><p>They can be useful as a cheap and fast approximation of a more expensive search. For example, Google at one point used them in Chrome to detect if a website was malicious; searching any URL in a database of malicious sites was too expensive to do for every website, so they instead used a bloom filter to quickly sift out most websites. If a URL was not found in the bloom filter, it meant it wasn’t in the database. If it was found in the bloom filter, that meant that it <em>could</em> be in the database, and so the expensive database check was done to make sure.</p><p>Bloom filters are nice for approximations of much more expensive operations. As we’ll see throughout this article, bit manipulation can be used to create quite a lot of interesting approximation techniques.</p><h4>How do they work?</h4><p>Take a bit vector of N bits. Set all bits to be zero. This is your empty bloom filter.</p><p>To insert an object, you first generate a hash of the object. Treating the hash as an integer, we can use it to select an index within the bit vector. Set the corresponding bit to 1. We have now inserted our object into the bit vector. If we want to check if an object is in the bloom filter, we simply hash it and check if the corresponding bit has been set.</p><p>Assuming we have a good hashing algorithm, we should have roughly a 1/N chance of getting a false positive.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZoRlJTnetk_3aXhSoBko3Q.jpeg" /><figcaption>Hashing objects A, B, C, and D, and selecting indices for our Bloom Filter from them. Notice that B and C overlap.</figcaption></figure><p>As we insert more objects, the chances of a false positive increase. Due to some properties of random numbers, a bloom filter with N bits will have roughly a 36.78% chance of a false positive after N element have been inserted.</p><p>However, we can actually improve this. Suppose we had a second bloom filter that used a different hash. In this case, the problem changes from finding one matching bit to finding two. Say we have a bloom filter with a 20% chance of a false positive. If we increase this to 2 bloom filters that both have to pass (and importantly use different hashes), then that probability drops to 20% * 20%, or 4%. If we increase this to 3 filters with a 20% false positive rate, that drops to 0.8% total. As we increase the number of hashes to check, the likelihood that any particular object will pass multiple filters drops exponentially with each additional filter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f0_lHELfvnjeq7C3cP8mYg.jpeg" /><figcaption>Hashing objects A and B, and generating two indices from each. Once again, there’s an overlap, but no worries; they have to overlap on all their bits for a false positive!</figcaption></figure><p>In practice, multiple separate filters aren’t used. Instead, we might have a Bloom Filter with N bits and K hashes, and set K bits for each inserted object. This means that the filter fills up K times faster (so make it K times bigger), but the odds of a false positive are actually a bit lower when what we have is essentially several large, overlapping filters rather than several small, independent filters.</p><h3>At the Heart of the Bloom Filter</h3><p>Let’s deconstruct the bloom filter a bit, and see if there are some unique properties we can steal.</p><h4>Mutable Constraint Models</h4><p>Constraint systems are like magic, even if they break a few rules.</p><p>Imagine you’re trying to design a rocket to go to Mars. How do you do that? You could spend a fortune, and direct thousands of engineers over several years to accomplish that goal. Or, if you had a smart enough constraint solver, you could give it some rules about physics, and a few constraints along the lines of “go from Earth to Mars within X months”, “limit G-forces to 3Gs” (to keep astronauts safe), and “cost &lt; $1,000,000,000”. And if it’s smart enough, it might spit out a rocket design in a reasonable amount of time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oqcazErKeq2MmKTuAmC8ZQ.jpeg" /></figure><p>That design might not be airtight (you didn’t add a constraint about that, now did you?), so all your astronauts might quickly asphyxiate, but other than that, it still seems to be a viable rocket design.</p><p>Constraint systems, simply put, are a declarative way of building things. You define the problem by listing requirements, and you get a solution by finding something that satisfies all those requirements.</p><p>Software that solves these kinds of problems exist. Look into SAT (Boolean SATisfiability Problems) solvers and SMT (Satifiability Modulo Theories) solvers for examples. Of course, in practice, solving these kinds of constraints is hard. Like, really hard. Typically NP (exponential time) or worse. Often, there are quite a lot of shortcuts that can be taken, and ways of making things much easier when certain assumptions can be made, making problems generally a lot easier than they look, though it can still get really hard in the general case.</p><p>Luckily, we’re not interested in “solving” the constraint system. Rather, we’re interested in detecting when something satisfies our constraints. It’s much easier to test if a particular rocket can go to mars than it is to design one that does. The reason why constraint solving can get hard is because sometimes the only way to find a solution is to check every possibility until you find one that works.</p><h4>Sum Constraints</h4><p>The specific way that Bloom Filters handle constraints is interesting, and opens up a lot of room for flexibility.</p><p>Here, the constraints are done with the bit vectors. If we have N bits, and assuming our hashing function is good, each 1 bit allows 1/N of the space of possible values through the filter. Each 0 bit blocks 1/N of the spaces.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wO1KhRvT_f53EjA7Efo_kg.jpeg" /></figure><p>It’s like we have N constraints we can toggle on and off (though typically in a Bloom filter, we can’t really safely turn a 1 bit back into a 0).</p><p>We could perhaps build something a bit like a Bloom Filter that used non-hashing constraints. We could, for example, build up a large set of rules that values we insert pass, and update those rules whenever we insert a new item. That’s hard though, and can get complicated really fast. The elegance of this constraint format is its simplicity. The hashes map random subsets of our input space to individual bits, which we can toggle on and off.</p><h4>Shadows</h4><p>Another thing we can notice is the effect that multiple hashes have. Even if an incorrect value happens to pass through one set of constraints, the odds of it passing another are pretty low. They get lower with every additional constraint we add.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rlCwYu5ABUlokZ3O180xkg.jpeg" /><figcaption>The shaded regions in the top two spaces are quite large, but the space where they overlap (as shown in the bottom space) is much smaller.</figcaption></figure><p>Another way to think of this is as such; the data we are storing in the bloom filter is a bit like a geometric object. However, rather than store the entire object, we instead store “shadows” of the object. Each new hash is a “shadow” from a different perspective. With enough perspectives, we can reconstruct a pretty detailed model of the object. The actual object isn’t the shadows, but rather some subset of the space where all of the shadows intersect.</p><p>There is some space where the shadows intersect, but where our object doesn’t lie. This is where our false positives come from. Of course, there are no places where our object lies, but where it doesn’t cast any shadows, so we don’t get any false negatives.</p><p>At this point, we’re not representing our problem by all the places it is, but rather we’re representing it with constraints, and by defining it in terms of known places where it isn’t.</p><p>As mentioned before, constraint systems can sometimes be really hard to solve. In this interpretation, “solving” is when we want to directly observe the object — translating between a collection of shadows, and the actual object they are cast by.</p><h4>Shadows of Dustclouds</h4><p>In practice, the shadows we generate from a bloom filter are actually rather unlike the shadows we see in real life. The objects we see in real life are rather continuous; they are made up of many points that are close together, with few gaps in between. This means that shadows are also quite continuous, and that a shadow isn’t just cast by a single point, but also by many of the points around it.</p><p>However, the space of possible objects we are working with are often quite big. Unfathomably big. Any object you insert into the bloom filter is just a single, extremely tiny point in that vast space.</p><p>Yet, it casts a shadow. If your bloom filter is N bits, and you use k hashes, each object takes up roughly (100 * k/N)% of that space. For a point that takes up such an infinitesimally minuscule space, that’s a big shadow. As a result, your bloom filter might start to fill up fast.</p><p>Another issue is that objects that are similar to each other will likely generate completely different hashes. So if you pack a lot of similar objects into the bloom filter, it fills up just as fast as if you insert random objects. Instead of nicely cutting up spaces like the diagrams in this article show, it’s like our hashing algorithms are tossing our space into a wood chipper.</p><p>So what if we change the hashing algorithm?</p><h3>Structure-Sensitive Hashing and Grid Filters</h3><p>Let’s say we want to use something similar to a bloom filter to approximate a problem where we’re working with continuous data. Say for example we want to check if a particular point is inside of some complex 3D object.</p><p>We can’t just iterate over all the points that lie within the object and insert them all into the bloom filter. There’s a massive number of individual points that will fall into there. Creating such a bloom filter would be extremely expensive, likely take exponential time, and would likely fill the bloom filter entirely, no matter how big we make it.</p><p>So let’s change the problem. Let’s use a hashing algorithm designed specifically to get us false positives, but mostly within specific circumstances that work in our favor.</p><p>Say we overlay a grid onto the object, and map every space in the grid onto a bit in our bloom filter. We can then use something similar to rasterization to fill in all the spaces in the grid that have at least some part that overlaps with our object. Such an algorithm would scale linearly with the number of spaces in our grid.</p><p>Of course, there will be some spaces on the grid where there is some overlap, but not much. So let’s rotate the object relative to the grid, then repeat the process to generate a second grid.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mFxukaJu55shVw_qRxe3xg.jpeg" /><figcaption>Left — a shape with only one grid to constrain it. Blue areas are false positives. Right — the same shape with a second grid (at a different orientation) constraining it in addition to the first. Blue and red areas are where only a single bit matches. Violet areas are where both grids overlap and create a false positive. As can be seen, this serves as a much better approximation. As the two grids are only 8x8 cells, this approximation would only take up 16 bytes (provided the orientations don’t need to be stored, e.g, they’re generated by a deterministic process).</figcaption></figure><p>This is similar to casting a shadow from another angle in the example we gave before. This has the effect of rounding off some of the sharp, stair-stepped edges of our object, and can cut out many of the spaces where there’s overlap.</p><p>Of course, this also changes the problem from one about shadows of dustclouds to shadows of more continuous objects. This means that “similar” points actually tend to create overlapping representations, and we only actually fill up the filter if we come close to filling up the entire space of possible values. In other words, if our object takes up a lot of space.</p><p>But if that’s the case, does it matter? If our object fills up most of the space, then most points will not only pass the filter, but will also wind up in our object as well.</p><p>Some other properties this has are that 1.) more “shadows” or “hashes” actually gets diminishing returns, rather than improving accuracy exponentially, and 2.) for this particular example, the size of the grid has a big impact on how small of details it can represent, so scale your grid accordingly.</p><p>It’s also worth pointing out that this way of representing shapes is actually vaguely similar to the way that the Grid Cells in your brain are known to represent location (by using multiple overlapping grids at different relative scales and orientations), but that’s an explanation for another time.</p><p>As far as I’m aware, I’m the first person to invent this data structure (though I’m skeptical of this claim; if anyone knows of it being used somewhere else, let me know!). As its [presumed] inventor, I’ll name it a<em> Grid Filter</em>.</p><h3>Sketches: Bloom Filters with Similarity Scores</h3><p>This next data structure is one that I’ve seen with a couple different names, so I’m going to refer to it with the simplest one, a “Sketch”. If you’ve heard of Sparse Distributed Representations, or Sparse Distributed Memory, those are other names for this.</p><p>If you’ve been following <a href="https://numenta.com/">Numenta</a> for a few years, you might recognize this. The original idea for this predates their work with it by a couple decades, but it’s all really from the same source.</p><p>For those who haven’t heard of any of this, this is all stuff from the realm of theoretical and computational neuroscience. We’re literally talking here about the data structures that your brain uses.</p><p>Suppose we want to create a hash of a data structure. However, we want objects with similar properties to produce similar hashes so that we can easily calculate similarity scores between objects.</p><p>What we can do is create some kind of function that detects simple features or properties of a data structure that we find significant, and then maps them onto indices for a bit vector. We can then set all bits in the bit vector that relate to detected properties.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-aCNdtsoj6ZE5g8kiHGtJg.jpeg" /><figcaption>The property being detected here is which colors of nodes are connected.</figcaption></figure><p>This can allow us to create compact summaries of data structures. It of course isn’t perfect. A large data structure packed into a small bit vector will lose a lot of information. Large data structures with a lot of variability will also likely fill most of the bits, making it hard to discern specific features. This approach also doesn’t store how many instances of a particular feature show up, just whether or not it does.</p><p>It’s also useful to consider what might be a “good” feature to track. For example, “The quick brown fox jumps over the lazy dog” includes every letter in the English alphabet, and thus would fill a bit vector that only looks at which individual letters appear.</p><p>If instead you look at subsequent pairs of letters, suddenly a lot of possibilities for rearranging a string disappear. In the aforementioned sentence, we have a lot of letters that only are ever followed by a single letter, meaning that we could reconstruct large portions of the string from just letter pairs. For example, if we see an <em>l</em>, we know it must be followed by <em>a</em>, then <em>z</em>, then <em>y</em>, and so on. We do eventually get to an o, which can be followed by <em>w, x, v,</em> or<em> g</em>, creating ambiguity.</p><p>At least when we’re dealing with relatively short strings, this preserves a surprising amount of structure in a relatively short bit vector.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oe7Pmszxe7HdgHg8q-w1mQ.jpeg" /><figcaption>Here, we look at several different properties on a colored, directed graph.</figcaption></figure><p>We can then of course also bring into account the “shadow” properties again, and represent an object with multiple feature sets. This also adds more ways to measure similarity between objects.</p><h4>Comparing Sketches</h4><p>If you have two sketches that have a lot of bits in common, then that implies that they have a lot of features in common too. This kind of comparison can be done quite simply by performing an AND operation between the two sketches to get the bits they have in common, and then a POPCOUNT operation to get the number of set bits that are left.</p><p>Another interesting property is that we can efficiently check for subsets. If we have sketches of two graphs, and we want to check if one is a subgraph of the other, we just need to check if its sketch is a subset. This is of course an approximation and will occasionally return false positives, but a couple of bitwise operations are <em>far</em> cheaper than actual subgraph checking algorithms.</p><h4>Building on Top of This?</h4><p>While I have yet to fully explore this space, I think there’s potential for more advanced data structures to be built on top of this. For example, if there were a way to perform a similarity score -based lookup, that may be useful for many applications.</p><p>I also think a tree-like data structure that allows for efficient lookup of subsketches would be useful. It appears as though such a data structure might be very useful for compiler optimization. This is something I’m looking into, but I don’t have anything concrete to show yet.</p><h3>Locality-Sensitive Hashing: Object Classification without Machine Learning</h3><p>Let’s say we want to do a similarity score-based lookup (k-NN style), and are willing to take a minor hit in accuracy (as in, we’re fine with occasionally missing a neighbor). Simply put; we have some set, and a sketch (or other input), and we want the top <em>k</em> elements of the set with the best similarity scores.</p><p>How can we do this efficiently? If we want perfect results, the problem unfortunately requires a linear search. However, when we can handle occasionally imperfect results, it turns out there’s a simple strategy based on hashing to do this; Locality-Sensitive Hashing.</p><p>If we have a dataset, we can imagine it filling some high-dimensional space. If our dataset consists of sketches, then each dimension actually represents a feature in our data.</p><p>The problem mostly becomes a matter of dividing up the space in a way such that points close together can be easily located in some kind of data structure. Interestingly, we can actually think of this a little bit like the Grid Filters we discussed earlier.</p><p>The Grid Filters work by looking at some object from a variety of random orientations and mapping each perspective to a grid. A point passes the filter if it matches with the object when viewed from every orientation. Let’s tweak that a bit.</p><p>Instead of mapping objects to grids at different angles, let’s instead divide the space in half with a random hyperplane. All points on one side of the hyperplane are one group, and all that lie on the other side are in the other group.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*RmpecxPloDKBM1XenINWMQ.jpeg" /><figcaption>With one hyperplane, we can divide a space in two. With n, we can divide it into 2^n spaces, and associate each one with an n-bit number.</figcaption></figure><p>Using bit vectors, the simplest way to create a hyperplane is to just check the value of a single, random bit. All the sketches where that bit is a zero lie on one side of the hyperplane, and all the sketches where that bit is a one lie on the other side. There are other ways of dividing up the space, but this is probably the simplest.</p><p>We can divide things further with another random hyperplane. With two hyperplanes, we actually get 4 categories. If we throw N hyperplanes at the problem, we can build up an N-bit hash for a given point by setting each bit to a 1 or a 0 depending on which side of the corresponding hyperplane it lands on.</p><p>Because two points that are quite close together are likely to land on the same side of each hyperplane tested (the only way this wouldn’t happen is if the points just so happen to be quite close to one of them, which does happen occasionally), we can use this to create a <em>locality-sensitive hash; </em>a hashing algorithm with many of the familiar hashing properties, but that mostly ignores minor changes in the data.</p><p>We can then also use this hash to place objects into a hash table. This table will likely have a lot of collisions, so we likely will want to choose an implementation that handles collisions efficiently.</p><p>Now suppose we want to do a k-NN search. We hash our input sketch with this method, and then perform a lookup in our hash table. We then look through all the elements returned, and filter out all but the k elements with the highest similarity scores.</p><p>We might also want to search “nearby” hashes. What this means is we not only look up our hash in the hash table, but also all the hashes that differ by only 1 bit. If we have an N-bit hash, that’s N additional lookups to perform. This might sound expensive, but it mostly solves the aforementioned problem of nearby points occasionally winding up on different sides of single hyperplane. It also isn’t that bad; if we have a 16-bit hash, we’ll have to do a total of 17 lookups (the original hash + the 16 hashes that differ by a single bit), compared to searching through the whole 65536 hashes across the table. If we have a large dataset, this is way better than searching through every possible object.</p><p>If we scale to larger hashes, the improvement is exponential. If we had a 32 bit hash, we’d only need to look up 33 total hashes, out of over 4 billion.</p><p>There’s still some chance of missing some values. While unlikely, it could be that two nearby points happen to fall on different sides of two different hyperplanes. Remember though that this technique is approximate; it doesn’t guarantee perfect results. If we wish to get more accuracy, we could always check more hashes; for example, every one that differs by up to 2 bits. Or we could go up to 3. Or more. Of course, this gives us harshly diminishing returns, as the likelihood of a mistake <em>drops exponentially </em>and the number of hashes we need to check <em>increases exponentially</em>.</p><p>This technique is actually used in production quite often. <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing#Applications">Wikipedia</a> gives a nice list of applications, but it’s generally quite good for “fingerprinting”, clustering, and classification problems that need to tolerate minor variability in data. In fact, most machine learning tasks amount to just fancy ways of solving these kinds of problems, so it’s quite interesting that we have a way to do it with no learning, and just hashing algorithms.</p><h3>Future Work</h3><p>I think there’s a lot of untapped room for experimentation here. These kinds of approaches are quite different from the common strategies that most programmers use, and show that there’s way more to Bloom Filters than people realize.</p><p>I think viewing these data structures as constraint systems is a useful perspective, and definitely needs more exploration. What kinds of other problems can we solve with similar techniques?</p><p>As we scale to larger and larger numbers of cores, we’re going to need to be able to keep all those cores fed with data. The problem is that computing power is much easier to scale than memory bandwidth, so the <a href="https://www.adapteva.com/announcements/epiphany-v-a-1024-core-64-bit-risc-processor/">1024-core CPUs of tomorrow</a> will need to be careful with how they manage memory, or they’ll spend more time waiting on data than actually working. Packing more data into less space is a great way to do that, and so investigating new ways of representing data will soon become very valuable.</p><p>I expect that Grid Filters may be quite useful in a lot of simulation and gaming applications, as performance is critical there, and geometric operations can be quite expensive. I’m also wondering; could there be other ways of doing these structure-sensitive hashes to approximate other types of problems?</p><p>So I’ll end this article with a call to action: investigate these kinds of techniques more and look for similar kinds of tools! There’s a vast range of algorithms and data structures left to be discovered, and these kinds of systems seem to hint at a new frontier.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7f62dd568373" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Programming in Hyperspace [pt.1]]]></title>
            <link>https://medium.com/@bzogrammer/programming-in-hyperspace-pt-1-726e5d416ba0?source=rss-7150ebf94b8f------2</link>
            <guid isPermaLink="false">https://medium.com/p/726e5d416ba0</guid>
            <category><![CDATA[bitwise]]></category>
            <category><![CDATA[number-theory]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Charles Rosenbauer]]></dc:creator>
            <pubDate>Fri, 01 Mar 2019 20:58:57 GMT</pubDate>
            <atom:updated>2019-04-13T21:29:07.749Z</atom:updated>
            <content:encoded><![CDATA[<p>Imagine programming as a type of problem, akin to a maze meets an obstacle course. You start at point A, an empty text file, and you need to get to point B, a finished, working application. Along the way, you’re met with many decisions, never certain which direction is best, and you frequently find yourself at an obstacle that must be overcome.</p><p>Perhaps you know the general direction to head, and have a few rules of thumb to make educated guesses. Perhaps you recognize some of these obstacles, and armed with prior experience, can confidently overcome them. Perhaps you even know how to find a few rabbit holes and secret passages, allowing you to sneak around an otherwise difficult obstacle with ease.</p><p>At your side, you carry your trusty toolbox, with everything you need to get around; you have your data structures, algorithms, and a few mathematical tools and functions. Of course, all your tools are composite; they are built from smaller tools, and often those are made of yet smaller tools. At the bottom of it all is the most fundamental tools; control flow, random memory access, and arithmetic. Everything else is just fancy combinations of these basic components.</p><p>You come across an obstacle. You have some options here. You can go left or right. You can try to scale it and go over. You can try to dig underneath. You can perhaps even attempt to plow straight through (brute force). All these basic options may be analogies for simple tools. If you’re wandering through some great labyrinth or making your way through some mathematical swamp, things may be harder, more complex. So you bust out the more complex tools for those — as you need a more complex path to get through such places.</p><p>But you recall that time you read about higher dimensions. Or that time you read Flatland. Or that time you tried reading that Stephen Hawking book, specifically the chapter on wormholes. Or that time you spent a weekend trying to learn machine learning, and attempted to grasp the idea of thousand-dimensional gradient descent. You wonder, is there another way to pass this obstacle? Is there some other direction I could take?</p><p>With every new dimension comes a new set of directions. In one dimension, you have left and right. In two, you gain up and down. In three, you gain forward and backward. With every new dimension, you gain more freedom to find your way around obstacles. So you ask yourself — what if you could take a step into hyperspace, into the fourth dimension, and find a shortcut along the way, via some new, mind-bending direction?</p><p>We can take a look through any CPU’s instruction set, and start looking for new tools. At first, we find all the obvious stuff — arithmetic and comparison operations, branch instructions, and load/store operations. Simple stuff. Then there’s some more sophisticated stuff; atomic and vector operations for working with parallelism, and interrupt management for working with the operating system, devices, and exceptions. Technically different stuff, but not fundamentally different.</p><p>Then you come across the arcane and strange tools of the Bit Wizards; AND, OR, XOR, NOT, SHIFTs and ROTATEs. Maybe you recognize those a little. Then you come across CTTZ, CTLZ, and POPCOUNT. And you wonder to yourself, is this what you’re looking for? Are the secrets of the fourth dimension hidden in these tools?</p><h4>Just some quick context before we proceed here</h4><p>I’ve been working on a quite ambitious programming language, on and off for the past couple years. It’s called Bzo. I won’t go into a long list of everything that’s planned for it here, but I will mention one insight I’ve had.</p><p>If you are offering developers nothing but the exact same set of tools they’re already accustomed to, just with a fresh coat of paint, then you’re not providing anything really valuable.</p><p>So I’ve been thinking about what I can provide in Bzo that will be unique, and different. The rest of this article is devoted to my exploration of bitwise programming, which is (among many other things) one of the “new tools” I want Bzo to provide (though few of these are actually “new”, rather just uncommon).</p><p><em>Note: This article is split into multiple parts, as it was getting quite long. I’ve saved the most exotic stuff for part 2, though perhaps you might consider some of the stuff here to be exotic too.</em></p><h3>Classic Bit Manipulation, and the Sheer Power of Your CPU</h3><p>I’ll assume from here on out that readers will already be familiar with the basics. AND, OR, XOR, NOT, SHIFTs, and ROTATEs. Those, and how numbers are encoded. If not, here are a few simple videos on the subject that should introduce them well:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FzMuEk44Ufkw%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DzMuEk44Ufkw&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FzMuEk44Ufkw%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/c2a9e95fc91512f536617ba3508b9ca6/href">https://medium.com/media/c2a9e95fc91512f536617ba3508b9ca6/href</a></iframe><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F-LNUXmMUMAM%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D-LNUXmMUMAM&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F-LNUXmMUMAM%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/b41011c0b8c823b739fa55d5ccad104d/href">https://medium.com/media/b41011c0b8c823b739fa55d5ccad104d/href</a></iframe><p>Note: “Circular Shifts” and “Rotates” are the same thing.</p><h4>CTTZ, CTLZ, and POPCOUNT</h4><p>Also, a few operations not mentioned are CTTZ, CTLZ, and POPCOUNT. CTLZ and CTTZ are “Count leading zeroes” and “Count trailing zeroes” respectively. They count the number of contiguous zeroes at the beginning/end of a number. For example:</p><p>CTTZ(00101000) = 3<br>CTTZ(10110000) = 4<br>CTTZ(00000111) = 0</p><p>CTLZ(00011010) = 3<br>CTLZ(00001101) = 4<br>CTLZ(11001100) = 0</p><p>These can be used for, among other things, figuring out the index of the highest/lowest set bit.</p><p>POPCOUNT counts the number of 1 bits in a number. For example:</p><p>POPCOUNT(00000000) = 0<br>POPCOUNT(00010000) = 1<br>POPCOUNT(00100111) = 4<br>POPCOUNT(11111111) = 8</p><p>This can be useful for a variety of calculations. Bitsets can utilize this for counting the size of the set, or the number of overlapping bits between two bitsets. There’s more that we’ll see in part 2 as well.</p><h4>Performance</h4><p>A typical integer on a 64-bit machine will take up 64 bits. In other words, that tiny piece of data that takes up a minuscule 8 bytes of RAM is an array of 64 boolean values. 64 of them. That’s pretty densely packed data.</p><p>Not only is it dense though, but your CPU can operate on all of those boolean operations in parallel. In a single operation. And, a bitwise operation is just about the fastest and most efficient operation your CPU can do.</p><p>Then you can take into account vector operations. AMD’s upcoming Zen 2 CPU architecture will have 4x 256-bit vector pipelines per core, and will scale up to 64 cores per CPU (for server models). Run the numbers, and that’s 65536 boolean operations <em>per clock cycle</em>. If the CPU runs at just 2 GHz, that’s <em>over 131 trillion boolean operations per second. </em>On a single CPU.</p><p>These operations are insanely fast and powerful, if you know how to use them.</p><h3>More Sophisticated Bit Manipulation</h3><p>This next section is full of number theory -type stuff, and is full of weird things you can do with multiplication/division/modulus on bit vectors. Perhaps it’s not extremely useful (though I find myself using these kinds of tricks occasionally), though it is something good to have in your toolbox when doing low-level programming. There may even be some unique applications for some of this stuff.</p><p><em>Note: Many of the examples in the next few sections rely heavily on the arrangements of digits/bits, so I’ve added extra spaces, horizontal bars (|) and zeroes into the numbers to emphasize these.</em></p><h4>Multiplying Bit Vectors</h4><p>Because multiplication is just repeated, shifted addition, we can use multiplication to perform a large number of addition and shift operations in a single operation. If we can line up our numbers in a way that we know that bits won’t overlap during the addition process, then the adds turn into OR operations.</p><p>In much the same way that 11 * 3 = 33, 111 * 3 = 333, and 001 001 001 * 15 =015 015 015 in decimal, we can do similar tricks with multiplication in binary.</p><p>A few simple binary examples (more in the following diagram):<br>001 001 * 011 = 011 011<br>001 001 * 101 = 101 101</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KpxLqpPc5vKf6Nwi3UKsFg.jpeg" /></figure><h4>Multiplication for Horizontal Addition</h4><p>We can also use multiplication to perform horizontal adds; partitioning numbers into groups of bits/digits, and then adding up partitions. An example in decimal would be 01 01 01 * 03 04 05 =<br>00|00|03|04|05 +<br>00|03|04|05|00 +<br>03|04|05|00|00 =<br>03|07|12|09|05</p><p>If we want to add up each partition (03, 04, and 05), we can see that the middle column in the example contains this sum. This all relies on our numbers in each partition not being too large as to carry digits into other columns. To get the column we want, we can apply a little bit of shifting and masking. Note that some of these columns may be lost due to overflow.</p><p>Once again, we can adapt this into base 2:<br>0001 0001 0001 0001 * 0011 0010 0100 0101 =</p><p>0000|0000|0000|0011|0010|0100|0101 +<br>0000|0000|0011|0010|0100|0101|0000 +<br>0000|0011|0010|0100|0101|0000|0000 +<br>0011|0010|0100|0101|0000|0000|0000 =<br>0011|0101|1001|1110|1011|1001|0101</p><p>The middle column is the full sum.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZG92QAq1di-fOcJP9y85uw.jpeg" /></figure><h4>Division and Modulus as Bitwise Operations</h4><p>As if things couldn’t get crazy enough with using multiplication for bit manipulation, we can use division and modulus as well! (Specifically, the unsigned integer versions)</p><p>The simplest case here is using them as an inverse of multiplication. If we can create repetitive patterns in bit vectors with multiplication, we can use division and modulus to detect and extract those patterns!</p><p>An example in decimal would be the inverse of one of the above examples. 333 clearly has a repetitive pattern. We can represent that pattern with the number 111, and divide 333 by 111 to test it. If the remainder is zero, we have a match, and the result of a division will give us the repeated pattern. If we search for a pattern that does not exist, we will get a non-zero remainder, and the modulus operation will alert us that our pattern detection has failed.</p><p>We can do the same thing with more complex patterns, for example 1501515 / 100101 will match as a pattern, and will return 15 as the repeated value. Because multiplication is commutative, we can also solve for the pattern by searching for the value. 1501515 / 15 = 100101.</p><p>Once again, all these fancy number theory tricks work in any base, including binary. So feel free to use it for bit tricks (though maybe keep this stuff contained, or in your own private projects rather than confuse your coworkers with tricks like this!).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ndhEG4cvDX0_WAuxHQFupg.jpeg" /></figure><h4>Modulus for Horizontal Addition</h4><p>Modulus can also be used for horizontal adds. I won’t go into the math behind this, but if you know a little number theory, you can probably figure it out yourself. Once again, this works in any base, so we can use examples in base 10 and generalize to get base 2 versions.</p><p>1 2 3 % 9 = (1 + 2 + 3) % 9 = 6<br>04 05 06 % 99 = (04 + 05 + 06) % 99 = 15</p><p>In binary now:<br>0011 0101 0001 0010 % 1111 =<br>(0011 + 0101 + 0001 + 0010) % 1111 = 1011</p><p>If we want to split the bit vector into N-bit blocks and add them, we take the bit vector mod ((2^N) - 1).</p><p>Unfortunately, modulus is actually quite an expensive operation and horizontal adds can be more efficiently done with some shifts and adds. You can still do this trick, but most optimizing compilers are aware of it, and will often optimize it to an implementation that does not involve modulus.</p><h4>Why?</h4><p>Perhaps if you’re doing some fancy bit manipulation, some horizontal adds might come in handy. Creating repeating patterns can occasionally be useful too (I sometimes find myself using it in my code), but I have a feeling it could have some minor applications somewhere else. Perhaps Digital Signal Processing or Compression?</p><h3>Exploiting Density</h3><p>A single byte can store 8 bits. 8 boolean values. If your CPU supports 256-bit vector units (as most these days do), you can fit a whopping 256 bits into a single CPU register. So what can you do with 256 bits?</p><p>Well, there are 2⁸ possible values that can be stored in a single byte. That’s 256. So, you can store 1 bit for each possible value of a single byte. What can you do with this?</p><p>Say we’re parsing some text. For the sake of simplicity, let’s assume it’s all in ASCII, so 8 (or technically 7) bit encoding. If we want to test if a particular string contains say, only lowercase letters, we can reduce this to just a lookup in a bit vector; a couple of bit shifts, an AND op, etc. There are probably even ways of vectorizing it for better performance.</p><p>In fact, we can pick any set of possible values for a byte, and easily generate a simple 256-bit value to represent it. We can then do fast lookups on that and use it as a filter for even complex patterns.</p><p>Suppose we take two pieces of text, and want to know the set of all characters they have in common? We can build up small bitsets of all the byte values that appear in each, and compare them with AND, OR, XOR, etc.</p><p>All of this is WAY faster than doing these kinds of operations on complex data structures full of pointers, and algorithms full of branching logic and loops.</p><h4>Exponential Space?</h4><p>Technically, all this takes <em>exponential space</em>. Typically, anything exponential causes programmers to run away in fear. In reality, everything has some value at some point. Exponential algorithms can actually be surprisingly useful in small, simple cases where overhead is low, especially because they are often much simpler than more “efficient” algorithms.</p><p>In fact, I’d argue that “inefficient” solutions can often be better than “efficient” solutions, mainly because that efficiency often comes with increased complexity, most often in the form of control flow and memory access, both of which can be incredibly expensive if they aren’t easy enough for the CPU to predict. But that’s a worthy of a whole other article. Perhaps many.</p><h4>Analysis on the Structure?</h4><p>There’s a lot more to this I think. Stuff with analyzing this kind of structure. It’s something I’d like to investigate more before I’m really ready to talk extensively about it. So instead of saying more, I think I’ll just leave one of my all-time-favorite talks here. Perhaps it’ll give you an idea of where the potential I sense in this is.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FC8--cXwuuFQ%3Ffeature%3Doembed&amp;url=http%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DC8--cXwuuFQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FC8--cXwuuFQ%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/6c1836ee8b3c48f85dc6a170be817e36/href">https://medium.com/media/6c1836ee8b3c48f85dc6a170be817e36/href</a></iframe><h3>“Quantum” Finite Groups</h3><p>Group theory is a pretty heavily-researched area of mathematics. Groups are abstract mathematical structures that show up in everything from modelling rotations to theoretical physics.</p><p>Suppose we have a finite bit set, say 64 bits. We can treat it as a number range mod 64. Let’s say we then set a single bit. We can think of this as storing a single integer set to that index. If we want to add/subtract with that number, we can rotate it left or right.</p><p>An addition-like operation is technically all we need to be considered a group.</p><p>However, if we set more than one bit, we suddenly find that we’re performing this operation on multiple values in parallel.</p><p>We can also create a variation of this where we can add multiple values in parallel. This can be done by ORing together the results of multiple rotates. In fact, if we had an operation in a CPU that was similar to a multiply, but performed rotates rather than shifts, and ORs rather than adds, we could easily have cheap hardware acceleration for this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1gaCZSB2te_wG9tJVm69IA.jpeg" /></figure><p>We also could throw in other bitwise operations, like AND, OR, NOT, and XOR for filtering, combining, and comparing these sets of values.</p><p>As a result, we can add/subtract numbers in a small finite group, simulating many of these operations in parallel. In a sense, we’d be doing something a little like the [flawed] pop-science description of quantum computing of simulating every path through a calculation in parallel. It’s quite limited in terms of scope, but perhaps there’s some interesting research to be done by going further down this rabbit hole.</p><h3>Upcoming in Part 2…</h3><p>Stay tuned for part two, where we’ll be getting into the really exotic stuff; Sketches, Shadows, and Locality-Sensitive Hashing. In other words, the places where bitwise operations, constraint systems, machine learning, computational neuroscience, and more all meet.</p><p>Edit: <a href="https://medium.com/@bzogrammer/programming-in-hyperspace-pt-2-7f62dd568373">Part 2 is here</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=726e5d416ba0" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>