Home › Forums › General Discussion › Product Suggestions

Code submission: convert(_,binary)

Posted on 2007-10-31 10:15 By DJKeenan (Maple Rating 2 191)
Categories:

I was recently asked what I thought of using Approximate Entropy in financial trading. I was not much familiar with ApEn; so I experimented a little.

A natural thing to do is consider long bit strings that are suspected of being able to (but not known to) pass general tests for randomness. Examples include leading bits of Pi, sqrt(2), etc. So I began with the following.

PiFive:=evalf[350000](Pi):
bits:=convert(PiFive,binary,1000000):

(Such things are helpful in various applications, not just studying ApEn.)

Maple takes days to compute the answer. Why? I had a look at the code. It turns out that the code can be improved; so I wrote a new version. The new version computes the above in minutes.

The code is plug-compatible, and is, here, offered to Maplesoft:

View 4119_convert-binary.mw on MapleNet or Download 4119_convert-binary.mw
View file details

‹ copying and pasting several lines of code into Standard Maple magnification ›
JacquesC's picture

Bravo!

Comment on 2007-10-31 11:07 from JacquesC (Maple Rating 4 1697)

Hopefully you will be successful, and others will be encouraged to do the same.

This can be sped up even more, by rewriting it in C (and using external call to get to it). But then again, this routine probably already exists in GMP?

calling C

Comment on 2007-10-31 11:22 from Tim Van Dusen (Maple Rating 3 212)

I wonder if everyone who uses maple and also codes in C, really knows how easy it is to create a DLL that maple can use. For those who may wonder... it really is VERY simple.

Is there an example here or in application center that shows this? I know that maple help shows how to do the maple end of things, but sometimes, people dealing with C compilers get confused by things like calling conventions and such when making a DLL for use by another application.

If not, maybe I can make one up, and make it available.

?OpenMaple,C,Examples

Comment on 2007-10-31 12:46 from Dave L (Maple Rating 2 128)

There is quite a bit of information on the topic of external-calling in the help-page, ?OpenMaple,C,Examples , and in the pages which it cross-references.

Dave Linder
Mathematical Software, Maplesoft

Axel Vogt's picture

Fine!

Comment on 2007-11-01 13:51 from Axel Vogt (Maple Rating 4 948)

Fine, i like that! Which of Knuth's book do you mean within your code?

NB: Tim, why not providing the above and explaining the conventions and settings for the various compilers in an own thread, say as complete example projects ready to use (Dave, i think that's what Tim may have meant)

Knuth: TAOCP

Comment on 2007-11-01 14:29 from DJKeenan (Maple Rating 2 191)

Thanks. See The Art of Computer Programming ( vol. 2).

using a DLL with Maple

Comment on 2007-11-01 17:10 from Tim Van Dusen (Maple Rating 3 212)

Axel, that's what I meant. It's really simple using OpenMaple to do lots of neat stuff, and it's pretty simple putting the code in place within a maple worksheet to call into a DLL. I was just wondering if some may have a problem with the creating of the DLL.

I'll try to put together some examples as you suggest. Perhaps one very simple one that just takes a value passed by maple, changes it, and returns. That sort of thing requires only a few files and a few lines of code in each.

Perhaps another that makes use of the GMP library. I use the Microsoft compilers and accessing the the GMP library with VisualC++ 5.0 statically is virtually impossible (it totally freaks out), while dynamically it's doable. While with Visual Studio 2005 it's no problem at all either statically or dynamically. My preference for DLL and windows device drivers is VC5.0 because it's quick and easy to do C++ style C stuff while the latter is kind of a pain for that sort of thing.

alec's picture

Mktime and next_permutation

Comment on 2008-06-10 23:22 from alec (Maple Rating 4 1476)

I have an example of using Watcom compiler supplied with Maple for creating a dll and using it from Maple, in my old blog post, Mktime.

Recently I added an example of writing a dll in C++ and using it in Maple as a comment in Joe Riel's blog, Faster Permutations.

Alec

acer's picture

a timing cross-over

Comment on 2008-01-21 02:22 from acer (Maple Rating 4 1357)

The existing `convert/base` code in Maple 11, without edits, can also be used to do some conversions to binary significantly faster than is done using Maple 11's `convert/binary`.

Q := proc(n)
parse(cat("11.",
          StringTools:-Reverse(
             StringTools:-Select(
                StringTools:-IsBinaryDigit,
                convert(convert(trunc(evalf[trunc(n/log[2](10.0))+2](
                                         Pi*2^(n-2))),
                                base,2)[1..-3],
                        string))))):
end proc:

On my 64bit Linux machine, the performance crossover between Doug's modified `convert/binary` and `Q` above looks to be about N=25000.

Repeat these examples below out of order, or separately. Use the `convert/binary/fraction` routine and its friends from the worksheet. As N gets to 400000 the routine Q gets about 10 times faster.

N := 25000:

gc():
st,ba,bu:=time(),kernelopts(bytesalloc),kernelopts(bytesused):
sol2:=convert(evalf[trunc(N/log[2](10.0))+2](Pi),binary,N):
time()-st,kernelopts(bytesalloc)-ba,kernelopts(bytesused)-bu;
                                                                                
gc():
st,ba,bu:=time(),kernelopts(bytesalloc),kernelopts(bytesused):
sol1 := Q(N):
time()-st,kernelopts(bytesalloc)-ba,kernelopts(bytesused)-bu;

If my sums are right, then one doesn't need more than trunc(N/log[2](10.0))+2 decimal digits in order to be able to obtain N binary digits.

The crossover point between Q and the regular system `convert/binary` routines in Maple 11 is about N=200.

I didn't look at improving the routines in the worksheet. Perhaps if one could get the address of the DAG of the floating-point number in Maple, and offset it past the DAG header, and copy it byte for byte into a hardware datatype Array, then that could used with hard-coded lookup tables. The lookup tables might contain hardware datatype Arrays as well.

acer

speed comparisons

Comment on 2008-01-21 10:42 from DJKeenan (Maple Rating 2 191)

I run Maple under WinXP on a Thinkpad. For n<5000, the routine in my worksheet is faster than Q. But absolute times are so small (e.g. 0.05 seconds) that the speed increase is unlikely to be worth worrying about. As n grows larger than 40000, the speed increase from using Q can be both a substantial ratio and minutes of real time. (The much better performance for larger Digits is presumably due in part to using GMP.)

Hence I think that acer's approach should be adopted in all cases.

JacquesC's picture

I have to wonder

Comment on 2008-01-23 21:48 from JacquesC (Maple Rating 4 1697)

if there isn't an even faster formula that does not go through base 10 at all (which is hard to convert to binary) but rather going through base 16 via the BBP formula.

BPP formula

Comment on 2008-01-24 04:29 from DJKeenan (Maple Rating 2 191)

Should this have been posted in the thread on decimal expansion of pi?

acer's picture

Bits package

Comment on 2008-06-09 14:41 from acer (Maple Rating 4 1357)

I would think that this can now be done even faster in Maple 12 using the new Bits package.

(edited: By "this" I mean conversion to base 2, not the original stated end goal of generating long bit strings with certain statistical properties.)

acer

alec's picture

Assembler code

Comment on 2008-06-09 15:03 from alec (Maple Rating 4 1476)

If a multiple precision number is written in usual format, as an array of (binary in computer) integers, the bits (i.e. binary digits) can be extracted using 2-3 lines of assembler code (by shifting). Then that can be accessed from Maple as in an example in my old blog post here, Binomial Coefficients mod 2. That, I think, would be the fastest way.

Alec

acer's picture

or just look at the DAG in memory

Comment on 2008-06-09 15:23 from acer (Maple Rating 4 1357)

This sounds similar to what I had suggested here (last paragraph). I actually implemented a rough version of this, which allowed me to extract the representation being used by Maple internally to store the GMP result of an evalf[n](Pi) call. And then a quick conversion to base 2 was easy. But I didn't bother to fix it up nicely for general use. I used an external call to DAXPY to copy the memory to an appropriate rtable, using an offset to the address of the DAG as the copying source. Presumably one could do the same thing using asembler, again using the address of the DAG of the stored GMP number.

The essence is just that Maple already has a nice internal representation in some 2^m base of the evalf[n](Pi) result, so there's not much more to do ideally than to examine just that.

Of course, as Jacques mentioned, there may be even better techniques working to directly generate a result in base 2^m, avoiding radix-10 high precision computation of the number as the initial step. That wouldn't be done in Maple proper, I guess.

acer

alec's picture

Sample

Comment on 2008-06-09 14:31 from alec (Maple Rating 4 1476)

The fastest way in Maple, probably, instead of using digits of Pi or sqrt(2), use

with(Statistics):
X:=RandomVariable(Bernoulli(1/2)):
Sample(X,1000000);

Alec

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}