Calculating an average.

A long standing bug in many algorithims is using the obvious


int m = (h + l)/2;


The problem with this is that (h + l) can overflow for large values of h and l.

One alternative is a cumbersome


int m = l + (h - l)/2;


Or the one I prefer is using >>> to perform an unsigned divide by two


int m = (h + l) >>> 1;


For example, say m, h and l where bytes and h = 100 and l = 90.

In the first case, h + l is -65 due to the overflow, so m = -32. (incorrect)

In the second case, h - l is 10, so m = 95 (correct)

In the last case, h + l is -65 or 10111110 in binary. Unsigned shifting right by 1 is 1011111 or 95. (correct)

Comments

  1. Unknown6 April 2015 at 09:55

    Hi Peter Lawrey,

    Thanks for the article, while grappling with content of this post I discovered the following things for myself
    • l + (h - l)/2 uses 3 operations and (l + h) >>> 1 uses 2 operations
    • (l + h) >>> 1 works only for positive numbers
    • We cannot generalize this logic, eg: 4 numbers and unsigned right shift by 2 digits

    -Mehar

    ReplyDelete

Post a Comment

Popular posts from this blog

Why You Should Tune Code Before Your Garbage Collector

Image
Optimising your memory allocations in Java could make far more difference than your choice of Garbage Collector and may even change which is the best garbage collector. In this post I look at a simple event to response latency benchmark, MarketDataSnapshot to NewOrderSingle at 50K/s for 30 minutes using JLBH to test Chronicle-FIX. The goal is to compare a system which is doing redundant work (in this case logging each message using SLF4J), compared with not logging (Chronicle-FIX records every message internally using Chronicle Queue) and how this changes the choice of Garbage Collector For the p99 (worst 1 in 100) the choice of Garbage Collector makes a different on par with optimising how loggin is done However, for the p99.99 (worst 1 in 10,000) optimsing how the logging is done is orders of magnitude more signifciant than the choice of Garbage Collector Unoptimised Benchmark This takes the optimised benchmark and adds one SLF4J log line of just ...
Read more

Asking multiple AI to optimise the same code

As different AIs are implemented differently, they don't all provide the same answer, nor do they consistently outperform one another. The best approach is to use multiple AI and pick the one you like best. My goal here is not to declare a winner based on one example, but instead to show the variety of answers you can get with different AI. I asked each AI to Suggest how to implement this more optimally private static String formatOffset(int millis) { String sign = millis < 0 ? "-" : "+"; int saveSecs = Math.abs(millis) / 1000; int hours = saveSecs / 3600; int mins = ((saveSecs / 60) % 60); int secs = (saveSecs % 60); if (secs == 0) { if (mins == 0) { return sign + twoDigitString(hours); } return sign + twoDigitString(hours) + twoDigitString(mins); } return sign + twoDigitString(hours) + twoDigitString(mins) + twoDigitString(secs); } private static String twoDigitString(int value) { ...
Read more

Which Doc Format is Best for AI Specifications?

I have a Spec Driven Project with 674 documents incl 181 specs, 429 tasks, and 40 project docs. About 1/3 of these are an acceptance sub-project to show the root project meets fit-for-purpose requirements. I used Fable to convert these to and from AsciiDoc, Markdown, and HTML. From this, I tried to draw some conclusions about which format is better than the others for AI specifications. TL;DR: Markdown for AI working documents, AsciiDoc for curated human-reviewed specs, HTML only as a publishing target. Objective Metrics Corpus Tokens (Approx) Markdown: 594k, AsciiDoc: 598K, HTML: 661k Worst Single-File Ratio AsciiDoc: 1.023x, HTML: 1.26x (due to tables and code blocks) Markup share of file content Markdown 0.9%, AsciiDoc 1.3%, HTML 9.9% - a 10x overhead for HTML Read/write Assessment In terms of readability, both Markdown and AsciiDoc are good. HTML has far more tags, which add noise. One of the most common tags is <code> some code </c...
Read more