It doesn’t.
It avoids division.

But the whole question of dividing by ten, specifically, was to avoid multiplication as well as division:

single multiplication may be 10 clocks or so, a huge improvement over old XT machines that needed several times more (60-140 cycles). and division was costlier than multiplication. so if you had to divide by some fixed number and fast, it was better to program multiplication by reciprocal. and for multiplication by some other common values like 10, one could combine couple of shift and add operations and still be faster than actual multiplication.

Now, I had interpreted that as being dividing by 10, hence multiplying by the reciprocal of 10 using shift and add operations.

But if @panic mode really meant multiplying by 10, that is very straightforward.

z = (z<<1) + (z<<3);

or

z <<= 1;
z += (z << 2);

So I think dividing by ten (which would be something that a cheap MCU might have to do a lot of in order to, for instance, convert values to BCD for display purposes) is a much more interesting example.

Even if we allow multiplication, the question of whether it is good enough comes into play (as it always must).

z = (x * 3277) >> 15;

only produces correct values until x = 16388. So it works as long as your numerator is no more than 14 bits (as always, the assumption is that we are talking about unsigned integers), which may well be good enough for some applications.

 

conventional way is to use a loop and check things one by one until one is found.
but more efficient way was to simply do two operations (per data register) and calculate.

A and (-A)

because this quickly returns bit position of the most important thing.

for example, something caused production to stop and there are several alarms, appearing as 28544

that is
0110 1111 1000 0000
while negative value (-28544) is
1001 0000 1000 0000

AND-ing those two values returns
0000 0000 1000 0000 which represents the unique thing (LSB is top priority, MSB is lowest...)

I haven't seen that trick before, but I can see a number of situations in which it might be very handy. I've got a couple in mind that I might explore a bit (no pun intended) when I get back home.

 

There are more than one way to skin a cat.

If you can anticipate the need to divide at some point, you can scale your values by 10 or any number of bits in order to preserve precision, what is known as fixed point integers.

I do °C and °F conversion, relative humidity, and dew-point calculations entirely using fixed point integers, no floating point calculations required.

You can also use BCD arithmetic which makes division by 10 trivial.

 

Another exercise is in calculating the logarithm function.
There is a short cut if you think about it.

Very often when displaying spectrograms, frequency response curves, etc., one needs to draw the log of a function.

 

Another exercise is in calculating the logarithm function.
There is a short cut if you think about it.

Very often when displaying spectrograms, frequency response curves, etc., one needs to draw the log of a function.

A lot depends on the representations being used and what base you need the logarithm to. Also, how good you need the logarithm to be.

For instance, if the number is represented as an IEEE floating point value, you can extract the exponent bits and that gives you an approximation of the base-2 log of the number. You could then do something like a polynomial approximation for the log of the mantissa and add that to the exponent. Converting to another base is then just a multiplication by a constant. You need to be careful to make sure that denormalized numbers are handled properly.

 

How would this be faster than actual multiplication, since it involves multiplication .

On modern PC-level processors, and probably on higher-end MCUs, multiplication is nowhere near as expensive as it used to be. But on lower-end MCUs, that is not the case.

Very well, here ya go, just shifts and adds.

uint64_t divide_by_10(uint64_t n) 
{
    uint64_t q = (n >> 1) + (n >> 2);     
    q = q + (q >> 4);                     
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;                           
    uint64_t r = n - q * 10;              
    return q + ((r + 6) >> 4);            
}

 

Very well, here ya go, just shifts and adds.

uint64_t divide_by_10(uint64_t n) {
    uint64_t q = (n >> 1) + (n >> 2);       // Approximate n * 0.75
    q = q + (q >> 4);                       // Refine estimate
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;                             // Final adjustment

    // Optional correction step
    uint64_t r = n - q * 10;                // Remainder
    return q + ((r + 6) >> 4);              // Round correction
}

How is that just shifts and adds? That the optional correction step involves multiplication, which would completely defeat the purpose.

Also, how optional is that correction step since, without it, it gives the wrong answer even for n=10?

 

How is that just shifts and adds? That the optional correction step involves multiplication, which would completely defeat the purpose.

Also, how optional is that correction step since, without it, it gives the wrong answer even for n=10?

Here:

uint32_t divide_by_10(uint32_t n) {
    uint32_t result = 0;
    uint32_t remainder = 0;

    for (int i = 31; i >= 0; i--) {
        remainder = (remainder << 1) | ((n >> i) & 1);
        if (remainder >= 10) {
            remainder -= 10;
            result |= (1U << i);
        }
    }

    return result;
}

Division by 10 is easy if the data is stored as packed BCD too, just right shift 4 bits, that's why IBM had decimal support baked into their hardware, a whole set of decimal instructions like ZAP.

 

Why is this loop with 32 iterations, 64 shifts 32 AND, 32 OR and 32 comparisons plus some additional stuff depending on the compare result written in C faster than a simple

result = n / 10;

where there compiler output is an optimized assembler (library) routine?

 

Why is this loop with 32 iterations, 64 shifts 32 AND, 32 OR and 32 comparisons plus some additional stuff depending on the compare result written in C faster than a simple

result = n / 10;

where there compiler output is an optimized assembler (library) routine?

Oh it isn't, of course it is not. But someone mentioned having to do divide in the old days using just shift and add operations, so we started dwelling on that challenge.

I have no real idea how a C compiler might do that (its' probably vendor specific) a Z80 or 6502 and some early ARM chips had no divide instructions, so a C compiler for those must have done some algorithm but probably not the one I posted.

 

at the time i filtered some input bit stream into an output one inside an ASM sub under (MS-D)OS i noticed that the final speed depended on "order of operations applied" (e.g. arrangement of solving logic) and the optimal block sizing

the latter (buffer/data-stack length addressing) might be comparable to a https://www.google.com/search?channel=entpr&q=asm+near+far+jump+cpu+clock+cycles -- it likely takes a comprehensive experience at one particular hardware/OS combination to be able to predict or work out the "at near optimum speed solver" ???

also reveals https://ppc.cs.aalto.fi/ch2/v3/ not sure if it's for any good for c coding

 

at the time i filtered some input bit stream into an output one inside an ASM sub under (MS-D)OS i noticed that the final speed depended on "order of operations applied" (e.g. arrangement of solving logic) and the optimal block sizing

the latter (buffer/data-stack length addressing) might be comparable to a https://www.google.com/search?channel=entpr&q=asm+near+far+jump+cpu+clock+cycles -- it likely takes a comprehensive experience at one particular hardware/OS combination to be able to predict or work out the "at near optimum speed solver" ???

also reveals https://ppc.cs.aalto.fi/ch2/v3/ not sure if it's for any good for c coding

God save us, that insane segmented memory model, what were Intel smoking back then...

 

Oh it isn't, of course it is not. But someone mentioned having to do divide in the old days using just shift and add operations, so we started dwelling on that challenge.

sorry guys... what i wrote could have been clearer if i added line break or similar. i could write it better had i thought it would be worth it. perhaps i should have...

i was trying to present few different examples of how one piece of code could be faster than another. so i provided just that - tring to show that on same hardware under certain circumstances one can still get faster results by simply changing how result is obtained. i did not think my words would be causing such confusion... and some of you sound like small challenge is not equal to fun....


there was time when calculating things that involve division by a constant, it could be more efficient to convert that constant into a reciprocal value and do multiplication. that alone would speed up operation 2-3 times. on something that only runs at few MHz that was a massive gain if it done many times.

multiplying by some constant also can be slow. this can be improved by combining shift and add operations. interestingly this means writing longer code that executes faster.

in some cases, similar can be applied when dividing by some constant. provided link shows several such examples:

not sure any more...it was 40 years ago. but there were solutions to many such optimizations, like here.

another way to speed up operation is to use lookup tables, either pre-calculate things or load from file.

btw, one totally amazing thing that started in the early 90s is the assembly demo scene. there were different competition categories, most had limits on size of executable but there was of course also one without size limit. anyone who was doing programming that needed performance was hooked. it is thanks to those efforts that we have multimedia at our fingertips on every device from PC down to an iPhone watch.

it was pushing the limits what could be done on hardware of that time. this is before video interface was standardized so a lot of programs using graphical interface from that era would require specific video hardware (must have graphic card A, B or C but not D or E... oh, you want sound, you must have sound card A or B...).

it was not just amazing to watch but to see how things were exploited (often the code was shared after competition), often creating custom video modes with different resolution of memory organization - all for the sake of performance.

 

It is easy to overlook how programming intensive graphics operations can be. This is another example how HW can make a huge difference on performance.

One of the HW features found in STM32 MCUs is bit addressable memory.

Imagine having to access a single bit in a memory mapped screen image without bit addressable capability. You would have to access an entire memory word, calculate a bit mask, and then perform a read-modify-write operation.

 

It is easy to overlook how programming intensive graphics operations can be. This is another example how HW can make a huge difference on performance.

One of the HW features found in STM32 MCUs is bit addressable memory.

Imagine having to access a single bit in a memory mapped screen image without bit addressable capability. You would have to access an entire memory word, calculate a bit mask, and then perform a read-modify-write operation.

I think I read about that memory feature last year, the ARM processors really do have some innovations.

 

It is easy to overlook how programming intensive graphics operations can be. This is another example how HW can make a huge difference on performance.

One of the HW features found in STM32 MCUs is bit addressable memory.

Imagine having to access a single bit in a memory mapped screen image without bit addressable capability. You would have to access an entire memory word, calculate a bit mask, and then perform a read-modify-write operation.

I wrote a 3D graphics app many years ago for home computers. It was wire frame (and could color polygon surfaces too). Well to animate was abysmal (written in (a poor) BASIC) so I devised a neat trick.

To animate say a wire frame cube I would draw the thing, then update the position and redraw, but what the redraw did was neat it first "undrew" a line (draw the original line in whatever the background color was) then draw the new line (which likely will have moved slightly) and repeat for all lines comprising the object.

It flickered of course but far far better than doing a clear-screen, draw new object approach.

 

There is another way to do it.

In our labs we had Lear Siegler ADM-3A CRT terminals connected via RS-232 to Data General NOVA 2 minicomputers running BASIC. These were plain text displays sold initially as a kit.



I created a board internally to add bit mapped graphics as an additional layer ORed to the text video stream.

From the BASIC language, the program was able to move the x,y address of the targeted pixel and then SET or CLEAR that pixel.

What I implemented in HW was the ability to XOR the pixel, i.e. bitblt commands on a single bit. This feature was added after having attended a lecture on SmallTalk given by Adele Goldberg from Xerox PARC.

By drawing wireframe images using XOR logic, you perform selective erase by simply drawing over the previous image. The entire HW logic to MOVE/SET/CLEAR/XOR a single pixel was accomplished using a 2764 UV-EPROM.

Then I wrote a Lunar Lander game in BASIC. I also did a screen saver with straight lines that move about the screen. One of these days I ought to fire up the Nova 2 and ADM-3A.

 

There is another way to do it.

In our labs we had Lear Siegler ADM-3A CRT terminals connected via RS-232 to Data General NOVA 2 minicomputers running BASIC. These were plain text displays sold initially as a kit.

View attachment 357402

I created a board internally to add bit mapped graphics as an additional layer ORed to the text video stream.

From the BASIC language, the program was able to move the x,y address of the targeted pixel and then SET or CLEAR that pixel.

What I implemented in HW was the ability to XOR the pixel, i.e. bitblt commands on a single bit. This feature was added after have attended a lecture on SmallTalk given by Adele Goldberg from Xerox SPARC.

By drawing wireframe images using XOR logic, you perform selective erase by simply drawing over the previous image. The entire HW logic to MOVE/SET/CLEAR/XOR a single pixel was accomplished using a 2764 UV-EPROM.

Then I wrote a Lunar Lander game in BASIC. I also did a screen saver with straight lines that move about the screen. One of these days I ought to fire up the Nova 2 and ADM-3A.

That's history man, very interesting.

Have you read: https://en.wikipedia.org/wiki/The_Soul_of_a_New_Machine

 

That's history man, very interesting.

Have you read: https://en.wikipedia.org/wiki/The_Soul_of_a_New_Machine

Yes. I have a copy on my bookshelf.

 

Yes. I have a copy on my bookshelf.

What about this one, a pretty good read, not as good Soul, but certainly interesting for tech minded people.



If they ever wanted to make a movie about Cray's life they would have chosen Robin Williams, alas that will now never happen.