Author Topic: Fixed point division?  (Read 7242 times)

0 Members and 1 Guest are viewing this topic.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #15 on: June 20, 2011, 07:37:09 pm »
Wow that was a fail.
*facepalm* *bangs head on table*
I never thought of using short ints in there. Thanks for suggesting that, now it works fine. This seems kind of inefficient, but it'll have to do for now, until i find something faster.
now, to work on division...
would this work?
a1 = upper half of a, a2 = lower half of a, in the same way as the multiplication routine
a / b = (((a1 << 16) / b) << 16 + ((a2 << 16) / b)?

Here's some C code:
Code: [Select]
inline long div(long a, long b) {
  long a1 = a & 0xFFFF0000;
  short a2 = a;
  return ((a1 / b) << 16) + ((a << 16) / b);
}
With my testing, it seems to work okay, but can someone confirm it?

I really wish ARM processors just had a damn FPU now.
« Last Edit: June 20, 2011, 07:59:33 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2898
  • Rating: +467/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #16 on: June 20, 2011, 09:37:07 pm »
Watch out that the low 16-bit part should again be treated as unsigned (or else you'll get weird stuff when bit 15 is 1). Technically, I think that method still loses some precision in the ((a1 / b) << 16) when compared to a higher-precision divide such as ((long long)a1 << 16) / b), due to the fact that you're shifting in 16 zeros whereas the long long division actually calculates the low 16 bits.

If you're that worried about performance you can always use the assembly routines I posted (the division routine takes about the same number of steps as a normal 32-bit division). I understand if you don't want to use them because it's for a contest, though. Then again, I'd let anyone use this code anyway.
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #17 on: June 20, 2011, 10:18:53 pm »
I would just use the routines with long long, but then I get compiler errors with newlib. Using your asm routines in a contest won't be a big deal, right? I might not have to use them, though, depending on how fast it runs.

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2898
  • Rating: +467/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #18 on: June 20, 2011, 10:21:41 pm »
I would just use the routines with long long, but then I get compiler errors with newlib. Using your asm routines in a contest won't be a big deal, right? I might not have to use them, though, depending on how fast it runs.
You'd have to ask the people in charge of the contest, I guess. I consider these routines to be like the built-in arithmetic operations except with fixed-point instead of integer. After all, the normal 32-bit division routine used by GCC was written by someone else, heh
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #19 on: June 20, 2011, 11:25:54 pm »
True, and I guess I am using the getPixel routine and all the others that bwang made.

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #20 on: June 22, 2011, 04:29:52 pm »
Yay, multiplication and division work now!  :D

Now, I have to get the engine to stop dividing by zero or I will be responsible for many black holes created inside calcs. :mad:
« Last Edit: June 22, 2011, 04:30:26 pm by fb39ca4 »

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #21 on: June 30, 2011, 09:39:08 pm »
Now that I think of it, shouldn't using unsigned short cause errors when I am multiplying negatives numbers, because say -0x0000.000F would be represented as 0x0000.FFF0 in the original number, and by using unsigned, the computer calc wouldn't be aware its a negative number.
« Last Edit: June 30, 2011, 09:39:52 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2898
  • Rating: +467/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #22 on: June 30, 2011, 09:41:12 pm »
Actually, it's represented as FFFF.FFF0, which is FFFF.0000 (signed -1) plus 0.FFF0 (unsigned). That's why the upper 16 bits is treated as signed and the lower 16 bits is unsigned.
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Fixed point division?
« Reply #23 on: June 30, 2011, 09:46:30 pm »
Oh, right. But anyways, wouldn't the fact that the bottom half is still signed, but not treated so in the multiplication routine mess stuff up?
I'm just going to do some experiments in visual studio and see what happens.
« Last Edit: June 30, 2011, 09:47:07 pm by fb39ca4 »

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2898
  • Rating: +467/-17
    • View Profile
    • TI-Boy CE
Re: Fixed point division?
« Reply #24 on: June 30, 2011, 09:50:18 pm »
Oh, right. But anyways, wouldn't the fact that the bottom half is still signed, but not treated so in the multiplication routine mess stuff up?
That's the thing, the bottom half isn't signed. Really, what determines signedness is whether the top bit means the entire value is offset by some 2^N. Of course, only bit 0x80000000 of the whole 32-bit value determines this, which means that any parts of the value not including that bit are unsigned, and parts that include it are signed. You can think of signed values having their top bit repeated infinitely to the left.
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman