Author Topic: Algorithms  (Read 3619 times)

0 Members and 1 Guest are viewing this topic.

Offline robonerd137Topic starter

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 1
Algorithms
« on: July 18, 2013, 03:26:41 PM »
Hey, this does not directly relate to robotics. I want to write an algorithm to do division using only addition and subtraction. Does anyone have an idea on how to do this, or maybe a link to someone who has already done something like this?

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,345
  • Helpful? 82
Re: Algorithms
« Reply #1 on: July 18, 2013, 04:51:41 PM »
Is this homework?

It's easy to do brute-force integer division:

Code: [Select]
int integer_divide(int a, int b) {
  int neg = 1;
  int ret = 0;
  if (a < 0) {
    a = -a;
    neg = -neg;
  }
  if (b < 0) {
    b = -b;
    neg = -neg;
  }
  while (a >= b) {
    a -= b;
    ++ret;
  }
  return ret * neg;
}

And, yes, this has trouble with the MIN_INT value, and also doesn't quite match what the CPU does when one of the values is negative, but it should show you the simplest way of doing it :-)

Offline waltr

  • Supreme Robot
  • *****
  • Posts: 1,944
  • Helpful? 99
Re: Algorithms
« Reply #2 on: July 18, 2013, 07:22:31 PM »
This is not uncommon for code in 8bit processors that do not have a hardware for multiplying.
I know that Microchip (maker of PICs) has a couple of App Notes on math routines and I'm sure if you tried a few google searches you can find lots more about doing this.

Offline robonerd137Topic starter

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 1
Re: Algorithms
« Reply #3 on: July 22, 2013, 02:36:40 PM »
@jwatte:
I am trying to do division of rational numbers not integers, but thank you anyway.

@waltr:
Thank you, I will look into that.

Offline jlp

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: Algorithms
« Reply #4 on: July 23, 2013, 10:35:43 AM »
Hello robonerd,

Division is only a series of subtractions where multiplication is only a series of additions and square root is a series of subtraction of escalating odd numbers, ex. 1, 3, 5, 7, 9, and so on.

For division, for instance 10/3, you will put 10 into a general purpose (a), you will put 3 into another register (b), and use another register (c) to count how many times you subtract 3 from 10 before register (a) is less than  register (b) and another register (d) for anything after the decimal point when register (a) is less than register (b)

In your algorithm, first you check register (a) to see if it is zero, if it is, you will jump out of your algorithm, "can't be done", if it is not zero then check register (b) to see if it is zero, if it is, you will jump out of your algorithm "can't be done".
Next, you will check register (a) to see if it is less than register (b), if is not less than, your algorithm will subtract 3, register (b) from 10 register (a), leaving register (a) with 7. After every  successful subtraction you will add 1 to register (c)
If register (a) is less than register (b), then the remainder will be stored in register (d), anything after the decimal point. Of course you will add another 0 to register (a) to continue a successful subtraction. Register (a) will now be larger than register (b).

Multiplication requires 3 registers, 2 for the two numbers you want to multiply (add) and the third register for how many times you need to add the two registers together checking third register for zero. Every successful addition you will subtract 1 from the third register until 0.

For square root, you will need 2 registers, for example square root of 25 is 5. You will take 25 register (a), and subtract 1 register  leaving 24. You will now add 1 to second register (b), number of times of successful subtractions until register (a) is zero. You will repeat this using escalating odd numbers, next will be subtraction of 3 then 5 then 7 and so on until register (a) is zero. You will see when register (a) is zero, the second register(b) will have completed 5 successful subtractions, thus the square root of 25 is 5. Again you must check to see if register (a) is less than the odd number you are subtracting just in case the square requires a decimal point.
Hope this will help
 


Offline robonerd137Topic starter

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 1
Re: Algorithms
« Reply #5 on: July 23, 2013, 12:20:33 PM »
Sorry that I haven't made this clear enough. I wish to know the algorithm for division of rational numbers. For example
1.25 / 0.4 = 3.125. What algorithm could I use to perform this division?

Offline jlp

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: Algorithms
« Reply #6 on: July 23, 2013, 05:53:51 PM »
What language are you using to write your algorithm ?
Sounds like you want to know how a calculator works.

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,345
  • Helpful? 82
Re: Algorithms
« Reply #7 on: July 24, 2013, 10:35:17 AM »
First, the numbers you show are decimal numbers, not rational numbers.
Second, if you know how to divide integers, you also know how to divide rationals (by doing several integer divisions) and how to divide decimals (by multiplying out by 10 for each decimal.)

Offline robonerd137Topic starter

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 1
Re: Algorithms
« Reply #8 on: July 25, 2013, 03:02:09 PM »
That is a huge derp. Sorry to all of you who have posted here, when I said rational I meant irrational. Just a silly typo that I repeated.

@jwatte 10:35:17
Let's say that I want to turn 5/4 into a decimal with an algorithm that can only use addition and subtraction. It would be easy to start off with performing the operation 5 mod 4 to see that 5/4 is greater than 1 but less than 2, but then I would be left with turning 1/4 into a decimal...

Let me change my question: I want an algorithm that turns a/b (where a, b are decimals and a < b) into another number c (which is a decimal), but this algorithm can only use addition and subtraction. Please let me know. If this is not possible what do I need to allow for in order to do this?

Offline jkerns

  • Robot Overlord
  • ****
  • Posts: 270
  • Helpful? 12
Re: Algorithms
« Reply #9 on: July 25, 2013, 06:50:39 PM »
Is this a computer thing, or just a random thing?

If this is a question about how to do this in a computer like device, your "decimal" number is stored as a binary number and you would do binary arithmetic and the first thing would be to understand how the number is represented in binary form.
I get paid to play with robots - can't beat that with a stick.

http://www.ltu.edu/engineering/mechanical/bachelor-science-robotics-engineering.asp

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,345
  • Helpful? 82
Re: Algorithms
« Reply #10 on: July 25, 2013, 08:04:40 PM »
Algorithm:
First, subtract b from a until a is less than b, counting the times.
This gives the number before the decimal.
Now, while you don't have enough decimals, and "a" is not 0, repeat the following:
- multiply a by 10
- subtract b from a repeatedly until it's less than a. The number of times you can do this is the next decimal.

If "a" ever goes to exactly 0, you now have a precise representation. Else, once you have as many decimals as you need, you have an approximation. (You can do one additional iteration to see whether to round the last digit up or down.)

Let's try this with a == 1 and b == 3.

First: subtract 3 from 1 until less than 3 -> 0 times. Integer part is 0.
Now, repeat:
- multiply a by 10 => 10
- subtract b from a untill less than 3: 10-3-3-3 = 1 => 3 times => first decimal is 3
- multiply a by 10 => 10
- subtract b from a until less than 3: 10-3-3-3 = 1 => 3 times => second decimal is 3
... repeat ...

Offline jlp

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: Algorithms
« Reply #11 on: July 26, 2013, 06:52:36 AM »
Hiya robonerd,

It doesn't matter what kind of numbers you are dealing with, whole, integer, rational, decimal, fractions, binary, hex and so on.

There is no silicon chip in the world that can perform a mathematical function beyond addition and subtraction.

Any mathematical function beyond addition and subtraction must be done with a algorithm using addition and subtraction ONLY, as all silicon chips (in the world, globally) only understand one thing. One's and Zero's.

All mathematical functions beyond addition and subtraction must be done using addition and subtraction.

Hope this clarifies what a silicon chip can do and what it can't do without the intelligence of human interaction.


Offline jkerns

  • Robot Overlord
  • ****
  • Posts: 270
  • Helpful? 12
Re: Algorithms
« Reply #12 on: July 26, 2013, 08:41:30 AM »
And shifting.

A shift is a multiply or divide by a power of two and is a lot faster than repetitive adding / subtracting.
« Last Edit: July 26, 2013, 08:42:57 AM by jkerns »
I get paid to play with robots - can't beat that with a stick.

http://www.ltu.edu/engineering/mechanical/bachelor-science-robotics-engineering.asp

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,345
  • Helpful? 82
Re: Algorithms
« Reply #13 on: July 26, 2013, 12:36:44 PM »
Any mathematical function beyond addition and subtraction must be done with a algorithm using addition and subtraction ONLY,

This is not true. Hardware support for multiplication and division is often implemented, for example using table look-up, or ganged barrel shifters. Yes, adders are probably part of the machinery -- they are necessary, but not sufficient.
« Last Edit: July 28, 2013, 03:03:27 PM by jwatte »

Offline jlp

  • Jr. Member
  • **
  • Posts: 11
  • Helpful? 0
Re: Algorithms
« Reply #14 on: July 28, 2013, 12:26:05 PM »
Just to clarify what a computer chip can understand, whether it be a controller or processor.

@jkerns, yes, shift left will double, and shift right will half. You cannot shift left or right with any numbering system except binary, what the registers can only understand. For example, if you load register A with C0h, the register will be 1100 0000b. Now do a shift left, the register will now read 1000 0000b which is 80h. Using shift instruction as a math calculation could be a bad thing unless you know the limitations of the registers, 8, 16, bit and so on. If you want to a multiply a number larger than the register can handle, you would have to pay attention to the "flag register" which can tell your program that you need another register to get the correct result.
Therefore a algorithm must be used.

@jwatte, Your comment, "This is not true" tells me that you are a bit confused due to your next two words "Hardware support". A math co-processor is a custom chip that is cut from doped silicon to perform specific math functions so the processor doesn't waste valuable cpu time. Still boils down to one's and zero's. Let's take a timer/counter built (cut) into a micro controller. In order to do a specific function you set the appropriate registers to the needs of a task. Registers are in binary whether you load them with hex, binary or what ever you choose . The bottom line is, the registers can only be in binary, one's and zero's.
Hope this help's.

Offline robonerd137Topic starter

  • Jr. Member
  • **
  • Posts: 18
  • Helpful? 1
Re: Algorithms
« Reply #15 on: July 31, 2013, 09:46:32 AM »
Thank you all for making this such an educational and entertaining thread. I am aware of the potentials/limitations/abilities of micro-controllers/CPUs. I had this question originally because I was trying to make a java program with an algorithm to perform division only using addition and subtraction, but I had a problem because if I did find that the digit in the thousandths place was a 3 then I would have to add 3/1000 to the answer variable, but that would require division. I now realize that a way to solve this problem is to make a Number class that stores numbers in Strings or Arrays so that I can manipulate the digits without division.

 


Get Your Ad Here

data_list