Hello, guys!
Today we will see 8051 assembly program to find the sum of first N natural numbers. There are two ways to compute the sum of N natural numbers. We will go through one by one.
First method: It’s simple basic code. Let’s go through the algorithm.
Today we will see 8051 assembly program to find the sum of first N natural numbers. There are two ways to compute the sum of N natural numbers. We will go through one by one.
First method: It’s simple basic code. Let’s go through the algorithm.
Algorithm:
- Start
- Store the value(N) up to which sum has to be found in a register(Ra)
- Initialize a register(Rb) to 1
- Enter the loop
- Add Rb and Accumulator register(A) and store the value in A
- Increment Rb
- Decrement and check whether Ra is zero
- If Ra is zero exit the loop and move value stored in A to destination register(Rd)
- Else, jump back and repeat the steps in loop
- Stop
here is an example code to find the sum of first 10 natural numbers.
Code:
ORG OOOOh
LJMP main
ORG 0x40h
main:
MOV R0,#0Ah ; N value
MOV R1,#01h
loop:
ADD A,R1
INC R1
DJNZ R0, loop
MOV R4,A ; Final result is stored in register R4
end
Second method: Using formula, It’s simple and faster way to compute the sum using formula
Sum=n(n+1)/2
No need of algorithm. Example code is showed below
Code:
Sum=n(n+1)/2
No need of algorithm. Example code is showed below
Code:
ORG OOOOh
LJMP main
ORG 0x40h
main:
MOV R0,#0Ah ; N value
MOV B,R0
INC R0
MOV A,R0
MUL AB ; n(n+1)
MOV B,#02h
DIV AB ; n(n+1)/2
MOV R4,A ; Final result is stored in register R4
end
[ Important: When to use which algorithm?
Use the first method when your N value is small so that machine cycles reduces. And use the second method when N value is large so that you can get the result at a faster rate.
I have discussed both the methods in order to give you an idea about optimization. We will discuss more about optimization in future posts.]
Use the first method when your N value is small so that machine cycles reduces. And use the second method when N value is large so that you can get the result at a faster rate.
I have discussed both the methods in order to give you an idea about optimization. We will discuss more about optimization in future posts.]
Edit:
Apologies if I was not clear in explanation part.
I have discussed the possibilities of achieving the sum of first N natural numbers. In the first method, your program size is reduced but you will have to compromise on execution time for large numbers (say numbers with 8bit size and above). Of course, the second method is simple to understand and remember. Use the second method to save time (Remember this method takes same execution time irrespective of the value of N).
"When to use which algorithm?
Use first method when your N value is small so that machine cycles reduces. And use second method when N value is large so that you can get result at faster rate."
Define "large" and "small". I'd advise to use the second algorithm on anything larger than 5, maybe 10 (not having counted CPU cycles, I could be off a little). So, in other words, simlpy forget method 1 and always used second method.
Isn't computing n*(n+1)/2 simpler and efficient?
Hello Rob,
As I have tested both the codes above, I observed one thing. For 3 bit number both of them takes almost similar time(around 0.00000655secs, That's hardly even a second). But as number of bits in N increases second method is best one. One thing I observed was program file size of second method is more compared to first one. May be optimization is also with memory concern, anyhow there is always trade of between speed and memory in optimization. For Embedded coder every aspect about program, file size and speed are main concerns. Panel is open for discussion and inputs.
"For 3 bit number both of them takes almost similar time(around 0.00000655secs, That's hardly even a second)"
First, that's FAR from "hardly even a second" (it's VERY FAR from a second) and second: that's exactly what I said; "3 bit numbers" are numbers 0..7. For any other number (assuming 16 bit that's 65536-7 numbers, assuming 32 bit that's 4.2 billion and assuming 64 bit that's even WAAAY more) the second method will outperform the first method. My point was that (assuming your 3 bit numbers conclusion is correct but hell, even maybe 4 bit numbers), assuming the input is distributed evenly across the whole spectrum of numbers, the second method may cost a few more bytes but will as-good-as-always, outperform the first.
"For Embedded coder every aspect about program, file size and speed are main concerns." And that is why I still maintain: *GENERALLY* the second method is best unless you only call the function with numbers 0..10 or something; in which case you will want the first method. But then again, a lookup table will probably be more efficient then.
True! I totally agree with what you say. I think the content of the post should be more refined. Use of formulas makes life simple.
Thank you very much. Cleared all my doubts.
Keep Going
After your edit it reads: "Use the first method when your N value is small". You should really DEFINE "small". 1000 is also "small" on a scale of 4 billion. But you should probably explain the O(n) vs O(1) nature of these algorithms (https://en.wikipedia.org/wiki/Big_O_notation).
As 8051 has 128 bytes RAM and 4K ROM and up to 64K external memory. It is not feasible for high end calculations. For billions of computations we have many Microprocessor like ARM Cortex etc.8051 is just basic thing used for simple stuff.
I think you guys (codes explorer) people you should have more embedded programs in cleaner ways and start tutorial with circuits. It would be very helpful for beginners in electronics community. Hope you people will do. All the Best
-Javed Kumar
Embedded Engineer
Pune, Maharashtra
Thank you Javed for your valuable input, we will work on that in future.