Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-pascal / 2009-10

two small ?s - high(real) and nearest 2^x

17 messages · 9 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

David Emerson

1. Is there a way to get the highest and lowest real values? I can do high(longint) but high(real) gives me an error. Also of interest is a low(real) value (-m * 10^n) as distinct from the smallest real value (m * 10^-n)

2. For the purposes of reserving memory in block sizes that can be easily reallocated, I like to use powers of two. So if I have, e.g., a dynamic array, I might start with a size of 1024 and then double it when it hits capacity. Hopefully this smoothes memory management, as I am using a lot of memory...

Anyway, what I'd like is a simple function that can quickly identify the next power-of-two larger than an arbitrary number. So if I feed the function 472, it will return 512. Thus far I haven't been able to figure out how to do this without a big if-then-else nest. Is there some clever way to request that the processor return the position of the leftmost '1' in 00101101?

Thanks!
~David.

Reply by email

Jürgen Hestermann
to David Emerson
Show quoted text 5 lines
2. For the purposes of reserving memory in block sizes that can be easily reallocated, I like to use powers of two. So if I have, e.g., a dynamic array, I might start with a size of 1024 and then double it when it hits capacity. Hopefully this smoothes memory management, as I am using a lot of memory...

I have done this too. I maintain 2 values, one for the *allocated* memory and one for the *used*. This way I don't need to reallocate unless I hit the border. If this happens, I simply allocate a new chunk of memory of double size (which is then again a power of 2) and move(copy) the data to the new memory. This way I don't have to reallocate very often because the additional memory increases by a factor of 2 which makes it less propably for large numbers of bytes.

Is there some clever way to request that the processor return the position of the leftmost '1' in 00101101?
The only way I can think of is a shr (or shl) loop which should run as
often as number of bits exist in the worst case;
i := 0;
while x0 do
    begin
    x := x shr 1;
    inc(i);
    end;
if i0 then
   x := 1 shl i
else
   error
if X=0 then overflow;

Reply by email

Anton Tichawa
to David Emerson: 1. Is there a way to get the highest and lowest real values? I can do high(longint) but…
David Emerson wrote 12 lines
2. For the purposes of reserving memory in block sizes that can be easily reallocated, I like to use powers of two. So if I have, e.g., a dynamic array, I might start with a size of 1024 and then double it when it hits capacity. Hopefully this smoothes memory management, as I am using a lot of memory... Anyway, what I'd like is a simple function that can quickly identify the next power-of-two larger than an arbitrary number. So if I feed the function 472, it will return 512. Thus far I haven't been able to figure out how to do this without a big if-then-else nest. Is there some clever way to request that the processor return the position of the leftmost '1' in 00101101?

On the processor level, if it is an x86, you can use "bsr" (bit scan reverse). Other processors may have similar instructions. I don't know if this is somehow mapped to an RTL function.

In pure pascal, use a loop to determine the magnitude, something like (omitting the details):

  repeat
    requested := requested shr 1;
    inc(magnitude);
  until requested=0;

Anton

Reply by email

Matthias K.
to David Emerson: 1. Is there a way to get the highest and lowest real values? I can do high(longint) but…
David Emerson wrote
1. Is there a way to get the highest and lowest real values? I can do high(longint) but high(real) gives me an error. Also of interest is a low(real) value (-m * 10^n) as distinct from the smallest real value (m * 10^-n)

As stated in the Documentation:
http://www.freepascal.org/docs-html/ref/refsu6.html The Real Type is Plattform dependend and either Single or Double. And since its IEEE Floating Point Representation, Low = -High (just a difference in sign bit)

You can find Max/Min Single/Double in unit math.
Sample:

uses math; ... WriteLn( 'Size: ', SizeOf(Real) ); if SizeOf(Real)>=8 then begin WriteLn( 'Low: ', -MaxDouble ); WriteLn( 'High: ', MaxDouble ); end else begin WriteLn( 'Low: ', -MaxSingle ); WriteLn( 'High: ', MaxSingle ); end; -- > 2. For the purposes of reserving memory in block sizes that can be > easily reallocated, I like to use powers of two. So if I have, e.g., a > dynamic array, I might start with a size of 1024 and then double it > when it hits capacity. Hopefully this smoothes memory management, as I > am using a lot of memory... > > Anyway, what I'd like is a simple function that can quickly identify the > next power-of-two larger than an arbitrary number. So if I feed the > function 472, it will return 512. Thus far I haven't been able to > figure out how to do this without a big if-then-else nest. Is there > some clever way to request that the processor return the position of > the leftmost '1' in 00101101? invalue := 412; -- outvalue := 1; while invalue 0 do begin invalue := invalue div 2; outvalue := outvalue*2; end; -- BUT.. this "allocation algorithm" may be good in theory (amortized performance for reallocation), but youre losing a lot of memory because of prereservation.. just for the records ;) regards, Matthias

Reply by email

Aleksa Todorovic
to Matthias K.
Matthias K. wrote 23 lines
On Sat, Oct 10, 2009 at 7:14 PM, David Emerson wrote: > 2. For the purposes of reserving memory in block sizes that can be > easily reallocated, I like to use powers of two. So if I have, e.g., a > dynamic array, I might start with a size of 1024 and then double it > when it hits capacity. Hopefully this smoothes memory management, as I > am using a lot of memory... > > Anyway, what I'd like is a simple function that can quickly identify the > next power-of-two larger than an arbitrary number. So if I feed the > function 472, it will return 512. Thus far I haven't been able to > figure out how to do this without a big if-then-else nest. Is there > some clever way to request that the processor return the position of > the leftmost '1' in 00101101? invalue := 412; -- outvalue := 1; while invalue 0 do begin  invalue := invalue div 2;  outvalue := outvalue*2; end; --

On x86 processors, there is bsr instruction which finds index of the most significant bit set. You just need some simple asm coding to use it.

Show quoted text 6 lines
regards,  Matthias _______________________________________________ fpc-pascal maillist  -   http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Aleksa Todorovic - Lead Programmer Eipix Entertainment http://www.eipix.com/

Reply by email

Matthias K.
to Aleksa Todorovic
Aleksa Todorovic wrote 29 lines
On Sat, Oct 10, 2009 at 20:58, Matthias K. wrote: > On Sat, Oct 10, 2009 at 7:14 PM, David Emerson wrote: >> 2. For the purposes of reserving memory in block sizes that can be >> easily reallocated, I like to use powers of two. So if I have, e.g., a >> dynamic array, I might start with a size of 1024 and then double it >> when it hits capacity. Hopefully this smoothes memory management, as I >> am using a lot of memory... >> >> Anyway, what I'd like is a simple function that can quickly identify the >> next power-of-two larger than an arbitrary number. So if I feed the >> function 472, it will return 512. Thus far I haven't been able to >> figure out how to do this without a big if-then-else nest. Is there >> some clever way to request that the processor return the position of >> the leftmost '1' in 00101101? > > invalue := 412; > -- > outvalue := 1; > while invalue 0 do > begin >  invalue := invalue div 2; >  outvalue := outvalue*2; > end; > -- On x86 processors, there is bsr instruction which finds index of the most significant bit set. You just need some simple asm coding to use it.

Yes, the same thing can be written with 3 instructions (bsr, inc, shl) for x86, but...

1. the code above is crossplattform compatible
2. with some size checks it can be assured, this code is only called if "current arraysize < new array size". So with a starting size of 1024 = 2^10, you need to call this code at most 22 times to grow a (4*SizeOf(array Element Type))GB array
3. the 22 times reallocation overhead is significant less performant..

so its a simple solution with benefits in compatibility

Reply by email

Marco van de Voort
to Matthias Klumpp

In our previous episode, Matthias Klumpp said:

Show quoted text 7 lines
Because PIC-Support is broken in FPC 2.2.4, I cannot build shared libraries at time. ( See http://bugs.freepascal.org/view.php?id=12492 ) Unfortunately it is not possible for me to switch to the development version of FPC, FPC 2.3.0. So, is there a patch for FPC 2.2.4 available to fix PIC? When does FPC 2.4.0 will be released?

Probably not this year, but early next. Note that 2.4.0-to-be is the same as the development version 2.3.x. So if you have problems with that, it might also be in 2.4.0

Reply by email

Matthias Klumpp
to Marco van de Voort
Show quoted text 13 lines
In our previous episode, Matthias Klumpp said: > Because PIC-Support is broken in FPC 2.2.4, I cannot build shared > libraries > at time. ( See http://bugs.freepascal.org/view.php?id=12492 ) > Unfortunately it is not possible for me to switch to the development > version of FPC, FPC 2.3.0. > So, is there a patch for FPC 2.2.4 available to fix PIC? When does FPC > 2.4.0 will be released? Probably not this year, but early next. Note that 2.4.0-to-be is the same as the development version 2.3.x. So if you have problems with that, it

might

also be in 2.4.0

I do not have problems with FPC 2.3.x, but it is not allowed for me to use experimental SVN software :-(
Early next year sounds good!

Matthias

Reply by email

David Emerson
to David Emerson: 1. Is there a way to get the highest and lowest real values? I can do high(longint) but…

Thanks, guys!

hrm, I am a little disappointed to realize that, although I'm on a 32-bit system, 'real' maps to 'double' rather than 'single' ... and it is a bit slower, too. So I guess I'll use single for now.

an fpc bsr function would be nice, but I'm gonna stick with compatible code.

I do realize that allocating by doubling size is memory intensive, but it's just for the rapid growth part-- once the array is populated, I shrink it down to its precise size.

Cheers,
David.

David Emerson wrote 12 lines
1. Is there a way to get the highest and lowest real values? I can do high(longint) but high(real) gives me an error. Also of interest is a low(real) value (-m * 10^n) as distinct from the smallest real value (m * 10^-n) 2. For the purposes of reserving memory in block sizes that can be easily reallocated, I like to use powers of two. So if I have, e.g., a dynamic array, I might start with a size of 1024 and then double it when it hits capacity. Hopefully this smoothes memory management, as I am using a lot of memory... Anyway, what I'd like is a simple function that can quickly identify

the

Show quoted text 13 lines
next power-of-two larger than an arbitrary number. So if I feed the function 472, it will return 512. Thus far I haven't been able to figure out how to do this without a big if-then-else nest. Is there some clever way to request that the processor return the position of the leftmost '1' in 00101101? Thanks! ~David. _______________________________________________ fpc-pascal maillist - http://lists.freepascal.org/mailman/listinfo/fpc-pascal

Reply by email

Schatzl Thomas
to David Emerson: 1. Is there a way to get the highest and lowest real values? I can do high(longint) but…

Hello,

Show quoted text 12 lines
2. For the purposes of reserving memory in block sizes that can be easily reallocated, I like to use powers of two. So if I have, e.g., a dynamic array, I might start with a size of 1024 and then double it when it hits capacity. Hopefully this smoothes memory management, as I am using a lot of memory... Anyway, what I'd like is a simple function that can quickly identify the next power-of-two larger than an arbitrary number. So if I feed the function 472, it will return 512. Thus far I haven't been able to figure out how to do this without a big if-then-else nest. Is there some clever way to request that the processor return the position of the leftmost '1' in 00101101?

Solutions with loops have already been posted, here one without any for completeness:

function next_power_of_2(v : dword) : dword;
begin
  // make sure that x <= 2^31 and x  0
  dec(v);
  v := v or (v >> 1);
  v := v or (v >> 2);
  v := v or (v >> 4);
  v := v or (v >> 8);
  v := v or (v >> 16);
  inc(v);
  result := v;
end;

Explanation: http://bits.stephan-brumme.com/roundUpToNextPowerOfTwo.html

Hth,
Thomas

Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla Firefox 3.5 - sicherer, schneller und einfacher! http://portal.gmx.net/de/go/chbrowser

Reply by email

Matthias Klumpp
to Marco van de Voort: In our previous episode, Matthias Klumpp said: It's not experimental anymore, it now has…
Show quoted text 9 lines
In our previous episode, Matthias Klumpp said: > > also be in 2.4.0 > > I do not have problems with FPC 2.3.x, but it is not allowed for me to > use > experimental SVN software :-( > Early next year sounds good! It's not experimental anymore, it now has a "fixes" branch label :-)

I decided to use this version of FPC for now. Thank you for your help! But now I have problems to compile the compiler:
First I got the error message

make[7]: *** No rule to make target `/prt0.as', needed by `prt0.o'. Stop.

So I changed the Loaders part in /rtl/linux/Makefile.fpc. Now I get

as -o /home/buildd/fpc-2.3.0/fpcsrc/rtl/units/x86_64-linux/prt0.o x86_64/prt0.as
as -o /home/buildd/fpc-2.3.0/fpcsrc/rtl/units/x86_64-linux/dllprt0.o x86_64/dllprt0.as
as -o /home/buildd/fpc-2.3.0/fpcsrc/rtl/units/x86_64-linux/cprt0.o x86_64/cprt0.as
as -o /home/buildd/fpc-2.3.0/fpcsrc/rtl/units/x86_64-linux/gprt0.o x86_64/gprt0.as
/usr/bin/ppcx64 -Ur -Ur -Xs -O2 -n -Fi../inc -Fi../ -Fi../unix -FE. -FU/home/buildd/fpc-2.3.0/fpcsrc/rtl/units/x86_64-linux -Cg -dx86_64 -dRELEASE -Us -Sg system.pp
systemh.inc(1054,2) Fatal: Can't open include file "setjumph.inc" Fatal: Compilation aborted

Does someone have an idea? (Or maybe I have missed something?)

Reply by email

Jonas Maebe
to Matthias Klumpp
Matthias Klumpp wrote 20 lines
On Sun, 11 Oct 2009 11:09:58 +0200 (CEST), (Marco van de Voort) wrote: > In our previous episode, Matthias Klumpp said: >>> also be in 2.4.0 >> >> I do not have problems with FPC 2.3.x, but it is not allowed for >> me to >> use >> experimental SVN software :-( >> Early next year sounds good! > > It's not experimental anymore, it now has a "fixes" branch label :-) I decided to use this version of FPC for now. Thank you for your help! But now I have problems to compile the compiler: First I got the error message make[7]: *** No rule to make target `/prt0.as', needed by `prt0.o'. Stop.

How did you try to compile it? I don't remember seeing this error message mentioned before.

Jonas

Reply by email

Matthias Klumpp
to Jonas Maebe
Jonas Maebe wrote 11 lines
On 11 Oct 2009, at 18:37, Matthias Klumpp wrote: > > I decided to use this version of FPC for now. Thank you for your help! > But now I have problems to compile the compiler: > First I got the error message > > make[7]: *** No rule to make target `/prt0.as', needed by `prt0.o'. > Stop. How did you try to compile it? I don't remember seeing this error message mentioned before.

Okay, maybe this only happens if you remove all Makefiles and run fpcmake again...
I tried it again and now - like magic - it works! But now I have another problem:
FPC 2.3.0 does not link against the new GDB 7 debugger:

(.text+0x38): undefined reference to `decimal32ToNumber'

/usr/lib64/libgdb.a(dfp.o): In function `decimal_to_number':

(.text+0x48): undefined reference to `decimal128ToNumber'

/usr/lib64/libgdb.a(dfp.o): In function `decimal_to_number':

(.text+0x58): undefined reference to `decimal64ToNumber'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x2230): undefined reference to `inflateInit_'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x226e): undefined reference to `inflate'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x2282): undefined reference to `inflateReset' /usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section': (.text+0x2295): undefined reference to `inflateEnd' /usr/lib64/libbfd.a(compress.o): In function
`bfd_uncompress_section_contents':
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:96: undefined reference to `inflateInit_'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:103: undefined reference to `inflate'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:106: undefined reference to `inflateReset'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:108: undefined reference to `inflateEnd'
fp.pas(575,1) Error: Error while linking
fp.pas(575,1) Fatal: There were 1 errors compiling module, stopping

Etc... Should I report a bug about this or does someone already work on this?
Thank you for your help again!

Matthias

Reply by email

Matthias Klumpp
to Jonas Maebe: How did you try to compile it? I don't remember seeing this error message mentioned…
Jonas Maebe wrote 11 lines
On 11 Oct 2009, at 18:37, Matthias Klumpp wrote: > > I decided to use this version of FPC for now. Thank you for your help! > But now I have problems to compile the compiler: > First I got the error message > > make[7]: *** No rule to make target `/prt0.as', needed by `prt0.o'. > Stop. How did you try to compile it? I don't remember seeing this error message mentioned before.

Okay, maybe this only happens if you remove all Makefiles and run fpcmake again...
I tried it again and now - like magic - it works! But now I have another problem:
FPC 2.3.0 does not link against the new GDB 7 debugger:

(.text+0x38): undefined reference to `decimal32ToNumber'

/usr/lib64/libgdb.a(dfp.o): In function `decimal_to_number':

(.text+0x48): undefined reference to `decimal128ToNumber'

/usr/lib64/libgdb.a(dfp.o): In function `decimal_to_number':

(.text+0x58): undefined reference to `decimal64ToNumber'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x2230): undefined reference to `inflateInit_'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x226e): undefined reference to `inflate'

/usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section':

(.text+0x2282): undefined reference to `inflateReset' /usr/lib64/libgdb.a(dwarf2read.o): In function `dwarf2_read_section': (.text+0x2295): undefined reference to `inflateEnd' /usr/lib64/libbfd.a(compress.o): In function
`bfd_uncompress_section_contents':
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:96: undefined reference to `inflateInit_'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:103: undefined reference to `inflate'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:106: undefined reference to `inflateReset'
/build/buildd/binutils-2.19.91.20091006/builddir-single/bfd/../../bfd/compress.c:108: undefined reference to `inflateEnd'
fp.pas(575,1) Error: Error while linking
fp.pas(575,1) Fatal: There were 1 errors compiling module, stopping

Etc... Should I report a bug about this or does someone already work on this?
Thank you for your help again!

Matthias

Reply by email

Jonas Maebe
to Matthias Klumpp
Matthias Klumpp wrote 19 lines
On Mon, 12 Oct 2009 12:49:03 +0200, Jonas Maebe < > wrote: > On 11 Oct 2009, at 18:37, Matthias Klumpp wrote: >> >> I decided to use this version of FPC for now. Thank you for your >> help! >> But now I have problems to compile the compiler: >> First I got the error message >> >> make[7]: *** No rule to make target `/prt0.as', needed by `prt0.o'. >> Stop. > > How did you try to compile it? I don't remember seeing this error > message mentioned before. Okay, maybe this only happens if you remove all Makefiles and run fpcmake again...

Regenerating the Makefiles in the fpc source tree is only supported when done with the latest trunk fpcmake. It is also not necessary to compile FPC.

FPC 2.3.0 does not link against the new GDB 7 debugger:

That's quite possible, since
a) GDB 7.0 was only just released
b) FPC uses libgdb.a from the GDB build process, which is not a supported interface to GDB anymore and hence no backwards compatibility is guaranteed in any way.

Compiling the IDE with integrated debugger support is hence only supported when using explicitly supported libgdb versions. See the defines in packages/gdbint/src/gdbint.pp to see which those versions are.

Jonas

Reply by email