Ultimate Lexicographical Indexing

[Colin Fiat]

Nice upgrade Ion, good looking forum. (You'll remember me as DemonSadist but I've been
using my real name for a couple of years now.)

Anyway, Lexicographical Indexing is always a fun thing for me and I believe I've created
the ultimate program.

I've examined many of your pages but have never noticed any limitation specifications.
80/20 Keno is the biggest combination I can see. But can you handle any quantity of
numbers up to 999999999 each or a maximum lexicographical index result of
1000000000000000000000000000000000000?

How long does your lexicographical function take to find the final index of a Keno 80 pick
20 game? (I'm guessing less than a millisecond.) What is the maximum you can take it?

My JavaScript lexicographical Indexer can handle the above limits and only starts to slow
down when indexing 50,000 pick 20 - it can take almost 3 seconds. For example, 20000
pick 100, using the numbers 200, 400, 800 and so on upto 20000, the lexicographical
index of 525115442340120097595878623282890266 was produced in 4 seconds.

Of course, if this were written in any decent language, millions of thousand digit numbers
could be indexed in seconds.

http://members.iinet.net.au/~htjs/temp/lexiindexbig.htm

[Ion Saliu]

Colin F, huh? Is it the same guy who said he was my “admiring friend and adversary”?

I never timed the speed of the calculations. Looks like the results are instantaneous in my software. Of course, nothing can be instantaneous!

Anyway, there are the compiler limits. My PowerBasic compiler has a limit of 18 significant digits. I can’t go beyond that data type accurately.

If I had a 64-bit compiler, I would be able to work with much, much larger numbers.

I don’t know what mathematical functions you use in your software. I looked at some libraries of math functions but I had no guarantee. I would trust if the functions were validated by a reputable organization, such as IEEE.

My software does lexicographical ordering for all types of sets, not only combinations. Also, my software generates all kinds of sets, not only combinations of numbers.

True 64-bit compilers, with huge data types, are badly needed.

”64-bit, Sixty-four,
Make us better than before;
32-bit, Thirty-two,
It was nice knowing you.”

Best of luck to you in your programming!

Ion Saliu
Lexicographical Order: Index, Rank, Algorithms, Combinations, Permutations
Combinatorics: Permutations, Combinations, Factorial, Exponents Generate

[Colin Fiat]

"admiring friend and adversary"? I am not sure I'd say that unless provoked. Oh wait,
you did ban me after my first 5 attempts at posting. So, maybe I did say that.

64bit compiler is not really necessary if you write you own large number handler. I
recently wrote 128bit functions for add, subtract, multiply, asc2bin and bin2asc. This
was for a VB6 project and the number handling was written in assembly so the speed
lost due to not using native 32 bit variables was negligible. Had I written the 4x32bit
number handler in VB then the program may have slowed a little.

The 4x 2^30 array I use in JavaScript did not hurt at all. The only difficulty was
changing all the single variables to a 4 element array and keeping track of everything.

[Ion Saliu]

Colin F:

You wear many hats! But forget about it …

64bit compiler is not really necessary if you write you own large number handler.

Big problem is: VALIDATION! Who validates the accuracy? I tried some of those “custom” math libraries only to discover a bunch of 0’s after some 18 significant digits! I tried also myself logarithmic tricks — but data was not reliable.

PowerBasic, the makers of potent compilers, don’t even dare to create huge data types. It ain’t an easy thing and validation is also expensive.

As huge as Microsoft is, they only created in VB6 a CURRENCY data type to handle 300 digits. That data type has had many detractors. I believe in its validity, however. If CURRENCY were inaccurate after 18 digits, Microsoft would have “died” after a deluge of lawsuits.

You show me your data types validated by IEEE and I will use them. You could even make some money by selling your libraries to PowerBasic, even Microsoft.

As of the ultimate software thing in your post, you should cover all types of numerical sets — first and foremost. Try first lexicographical order for a game like Euromillions. It is easier for you than it was for me: You have my software as a validation tool!

Best of luck!

Ion Saliu

[Colin Fiat]

No, the program itself is not the ultimate - the technique is. By comparison, a very
simple C++ function to index the last combination of 729c17 can take a couple of
seconds using n!/k!(n-k)!. My JavaScript version takes just under a second and a VB6
version can churn through more than 16000 per second.

IEEE is not required. I learned a valid method of summing big numbers in early primary school.

 12345
+67890
 80235

Taken a byte at a time:

  250  64 172 224  = FA 40 AC E0 = 4198542560
+   5  96  55 207  = 05 60 37 CF =   90191823
  255 160 228 175  = FF A0 E4 AF = 4288734383

Using digits 0 to 9, or bytes 0 to 255 or 32bit digits 0 to 2^32-1 makes no difference.

Multiplication is exactly the same. Subtraction and division require a little more effort
but not much. And as for validating them, use string manipulation to manually work
out the answer of a random equation using paper and pencil method and compare to
a 128bit method. Repeat a million times and alert on error. No IEEE validation required.

additional:

Assembly source code for adding two 128bit numbers stored as big endian composed
of sequential little endian dwords:

bigAdd proc STDCALL dest:DWORD, src:DWORD
      mov   edi,dest           ; destination address
      mov   esi,src            ; source address
      xor   ecx,ecx            ; zero all of ecx and clear carry flag
      mov   cl,4               ; count 4 dword addresses
lp00: mov   eax,[esi+ecx*4-4]  ; get one surce dword
      adc   [edi+ecx*4-4],eax  ; add and carry source to destination
      dec   cx                 ; decrement counter (not affecting carry flag)
      jnz   lp00               ; loop and next two higher level dwords
      ret
bigAdd endp

[Ion Saliu]

Colin F:

Go for it, super crocodilule! You can make BIG money! Convert your assembly routines to data types and sell them to compiler companies, including Microsoft!

Regardless how precise third-party math routines might be, ultimately it is the compiler that spits out data. That final data is always limited by the data types supported by the compiler.

Many programmers got FOOLED by third-party math libraries that claimed huge data types. In the end, there was NO PRECISION beyond the 18-digit limit (as in PowerBasic). The libraries can spit out 2600-digit long numbers — but there is no precision guarantee beyond 18 digits IF that was the data type limit in the compiler!

Here is a Basic interpreter that claims huge data types: UBASIC. I read a presentation like this:

“UBASIC is a BASIC-like environment which is suitable for number theoretic investigations. Version 8 of UBASIC has the high precision real and complex arithmetic (up to 2600 digits) of previous versions…”

Huge Microsoft only offered 300-digit wide numbers in Visual Basic 6. You can bet baby milk money that Microsoft would have acquired UBASIC many years ago!

But, then again, if you are 100% confident in the PRECISION of your routines, go for it. Microsoft or other compiler makers could make you really rich…

Please come back when you are ready in your endeavor.

Best of luck!

Ion Saliu

[Ion Saliu]

By the way –

Why do you stop your routines at 36-digit width? Why not go beyond Microsoft and create 512-digit-wide numeric data types (2 ^ 9)? After all, the same principles apply, right?

The link you posted only calculates the lexicographical index for a given combination. Why not add the complementary function and generate the combination for a given lexicographic index? That way, we could enter a very large lexicographic rank and see what combination we get.

You already visited my Web page where I published the source code for both types of functions (the first one is not mine):

Algorithm to Calculate Combination Lexicographical Order, Rank, Index, Software

Anyway, I would very happy if you would succeed with HUGE numeric data types (like 512 digits in length). I appealed to the PowerBasic guys for many years now to compile HUGE numeric data. My posts in their forum always started with the kokostirks over there … overreacting: “Why da hell do you need huge numbers, wider than 18 digits?”

I also appealed to them to upgrade their compilers to true 64-bit. It’s time for 64-bit computing. What a huge step computing took when it moved from 16-bit to 32-bit! A great increase in performance, plus working with much, much larger data sets! We all was very happy soon after Windows 95. The 32-bit compilers followed the day after …

I mean it, I’d be very happy for you to succeed with very HUGE data types. At least, you should try to convince PowerBasic to make their largest data type 36-digit wide (instead of just 18 now).

Best of luck!

Ion Saliu

[Colin Fiat]

Thanks for the encouragement Ion,

The JavaScript is limited to 36 digits because no browser is capable of handling that
much; remembering JavaScript is a interpreted language. I tried 20000 pick 200 and
while it did eventually come up with the correct answer, it took 20 minutes of hard
drive hammering by the browser to manipulate 1.6gb of data. I have no idea what it
was doing, maybe making copies of the arrays I replace each calculation?

The assembly version uses only 128bits due to being the greatest data size I required
at the time. it can be extended easily if required.

3 primary arithmetic functions are all I required, add, sub and mul. Division was not
needed and so I have yet to write it. But with 4 basic functions, almost every other
calculation can be derived. They also cover everything I can imagine with lotteries.

The GNU MP Bignum Library and MatLab are two large math libraries amongst many -
one for every language I guess. I vaguely remembering seeing one for JavaScript or
was that part of Ajax or jquery? Cannot recall but I need none of them for the simple
task I set myself.

Reverse Index calculation is most likely possible using my approach but I've not
stopped to work it out. Testing two subset numbers and adding the difference of
huge numbers from a table is simple. The reverse requires comparing two very large
numbers from the table. However, now that you've reminded me where I can find the
algorithm for a standard technique, perhaps that will be easier.

You should try creating your own inhouse functions for large numbers. Just like in the
JavaScript version, keep an array of decimal under 2^30, use the add and carry
method and when ready for display, each element in the array appended into one
string is the answer. No conversion from array specific formatting to decimal, just
string them together.

So far I've never used any third party library functions (aside from MicroSoft Kernel
routines) and probably will not. They come with a huge array of extra baggage I'll
never use and may even force me to write some code to suit their methodology
rather than letting me do my own thing.

[Ion Saliu]

Colin F:

Finally, I just found a 64-bit Basic compiler: PureBasic. Maybe you and other programmers in this forum will find it useful:

(Link removed)

The compiler creates TRUE 64bit applications, unlike the 32bit/64bit hybrid Microsoft offers in Studio NET. The editor has a CLASSY look — reminds me of Visual Basic 6. PureBasic editor has a more modern appearance, however. Probably the European stylish thingy!

Now, some of the members in the PureBasic form point me, as you did, to third-party mathematical library. But, again, there is no reference to the very important issue of validation:

(Link removed)

In any event, I will try PureBasic with some math programs I will convert from PowerBasic. Everything will be 64-bit software.

Best of luck!

Ion Saliu

[Ion Saliu]

Caveat – It is NOT a BASIC compiler!

“PureBasic” is, actually, an oxymoron: There is no Basic in it anymore! It should be called “Hybrid CBasic”. It looks a lot like C.

They removed ALL real (traditional) Basic keywords: CLS, COLOR a,b, LOCATE X,Y, PRINT “text”, OPEN “filename” FOR INPUT/OUTPUT/APPEND, PRINT #n, a;b;c;d, etc. The renowned Basic keywords were replaced by C-like functions — which are cumbersome and sometimes inflexible. For example, simply printing lottery combinations is so bad that lottery programming is virtually a NO-NO with this compiler.

It doesn’t have the HUGE data types I looked for. The applications created in “Not-Pure-Basic” are truly 64-bit, however. You can’t run them in a 32-bit operating system.

I had expected that 64bit software would be faster than 32bit software by an order of magnitude. In fact, it was slower. With great difficulty, I created a simplified lottery generator like in the source code published at SALIU.COM. The way it writes to files is cumbersome and slow. Some guys over there already got at me. They probably write only Hello, World-type of programs. Let them try a lotto program that crunches millions of combinations in thousands of operations!

To me, “PureBasic” is more like a project created by nerds! It might make sense for those who start programming from scratch. They can create Windows applications after a while. But the documentation is … just about 0.001% of the books written for Microsoft Basic’s!

“PureBasic” does have a stylish editor and GUI generator. But it is NOT BASIC — I’ll stick with my basics! I wouldn’t have been able to write all my software (unique and powerful) without my basics.

True Random Numbers Generator: BASIC Programming Source Code

[Ion Saliu]

Forget about that PureBasic! It represents a form of deceptive marketing. PureBasic relies on the great popularity of the BASIC programming language. It wants to attract new kids on the block, who want to learn programming. What could be easier than Basic?!

PureBasic , however, has absolutely nothing — no command whatsoever — in common with the Basic programming platform. The group selling PureBasic admits now publicly that they do NOT sell a BASIC language, but a C-like language!

Worst, the “place” is a slum populated with freaks, sick bullies, even whores! I only posted a couple of messages when they started the flame wars and attacks against me — that even before I said that PureBasic was anything but Basic programming! It got really nasty in there — and, of course, I do kick major butt when attacked! Public service on my part — keeps the world cleaner! I have cured a number of sick bullies in the virtual world in the past decade and a half. I even received a couple of private emails from them (signed freak) that Gmail warned me they may be phishing!!!

I asked them to try to generate to disk all combinations of 49 numbers taken 6 at a time. In a TRUE Basic compiler, you accomplish that with fewer than a dozen lines of code (including setting the screen colors). I was honestly disappointed with PureBasic handling of such important but simple matters. Of course, I got no answer. They don’t program anything with PureBasic, except for “Hello, world!”

Another truth is, the freaks did create a good-looking editor! Perhaps like those retarded kids capable of interesting-looking paintings …

Truth is, I really wanted a 64bit compiler — but only a TRUE Basic compiler. I have written lots of programs with thousands of lines of code each. It is now extremely difficult to convert the source code to a programming platform that’s very different from traditional Basic. Maybe later … or, maybe, never! I got great software already written …

[Colin Fiat]

Pure Basic sounds like many claims but no substance. Perhaps the 'community' there
have all had a small part to play in its creation and will defend their creation no
matter the ghastly mess they made?

Manfred Stampe and I worked on a potential new method for generating cover
designs. His idea was quite unique. He needed a little help with a few minor sections
that had grown difficult to manage. The end result was reasonably acceptable except
for one small detail - while certain set sizes were processed very quickly and
produced close to minimal cover designs, other closely related sets churned for half a
minute and produced excessively large sets.

The point of the story is that he used GFA-Basic. Even though the GUI is often times
clumsy and counter intuitive, the executables are blindingly fast.

[Ion Saliu]

I knew about GFA-BASIC several years ago, when I was working with Visual Basic for DOS (VBDOS). GFA-BASIC was considered more powerful but harder to use than a Microsoft Basic. I quickly forgot about GFA-BASIC when Visual basic (for Windows) became 32-bit. Then, PowerBasic came along as a 32-bt compiler. Surprisingly, GFA-BASIC is now FREE!

Right now, I’m interested in 64-bit programming only and only REAL (traditional) Basic. Basic should make the transition of my source code as easy and as fast as possible. As of 32-bit, I was hit by an insurmountable roadblock: File sizes over 2GB. All combinations in Powerball, for example, generate a file of over 4GB!!! That's why I wanted a 64-bit compiler ...

So, Colin F, you still work on lotto wheels (or covers, or lotto designs)! I am sure now. There is no rule or formula as of the size of a lotto wheel. The sizes are variable and larger than the sizes calculated by the lotto odds. You started a specific thread in my previous forums:

Lottery Lotto Gambling Software Systems :: View topic - Developement Software: exploring Cover Designs C(v, k, t)

The only method to generate lotto wheels of the size equal to the odds is via LEXICOGRAPHICAL INDEXES. But such lotto wheels do not meet the minimum guarantee every time the wheel “hits”. On the average, however, the minimum guarantee is met. Simplified, it happens like this. 2 wins, followed by 0 wins; average 1 win.

Lotto Wheels, Lottery Wheels on Lexicographical Indexes Software

Best of luck!

Ion Saliu