A Replacement Calculator for Casio's with RPN!



#2

Hi,

I bought one of these Casio fx-9860g slim calculators - I like the shape.

It's a convenient form factor, folds up neat and fits in your pocket, with the screen protected so you don't need an outer case. Despite claiming to be slim, it's depth and height are about the same as a hp50g, but the length is significantly less. The screen is quite clear and the buttons work well. There's also a backlight and a USB connector.

However, i don't much care for Casio's actual calculator. So i've been developing my own "replacement" calculator called Reckon. It's not finished yet, but i made a sneak preview video if you want to have an early look.

It also does RPN!

VID (fuzzo-vision): http://www.youtube.com/watch?v=-uBY8kbyKEE

[NB: on the vid, the graphing is blurred. this is a framerate alias. it's not actually like this!]

I'm hoping to release a beta into the wild around the end of this month.


#3

Very nice and quite fast.

#4

GREAT! I was just about to start in of my own app for this calculator, but I was thinking more along the lines of something programmable, a FORTH-like language.

Since you say that it's 25 decimal digits I assume that you wrote your own math routines. Did you figure out how to call any of Casio's built-in functions other than those provided in the SDK?

-Katie


#5

It could do with a better program language. Casio has that weirdo basic-alike but not really language that they've had for years. It would be really easy to port another language. LUA would be very easy.

one thing tho': It's got a lot of flash memory for code but only 64k of ram. this puts the kibosh on anything too fancy.

I do use all my own math routines, although you do get the IEEE754 float/double library with the SDK. I used mine because, in any case, it's software emulation and mine are decimal floats.

There are a lot of undocumented syscalls out there. Various people are endeavouring to discover them and make them public. I have used a few already, such a nonblocking keyboard read and locating the screen RAM.

Its not a bad little machine to program.


#6

Quote:
I do use all my own math routines, although you do get the IEEE754 float/double library with the SDK. I used mine because, in any case, it's software emulation and mine are decimal floats.

Why not the IBM decNumber library? Last time I looked it was way better at packing things for a low memory (RAM) devices.

8 byte reals gives you 16 digits. 16 byte reals are 33 digits long. Plus infinities, not numbers, sub-normals. I.e. IEEE 854 decimal floats.


- Pauli


#7

Hi,

The decnumber library does not operate internally in the packed form, you have to unpack, operate and then pack to use this form.

This would raise the question of whether i should always perform this triple - which would impact performance, or only to pack when i store in variables etc.

However the variable storage is on the heap, so usually this means sizes are a multiple of 4. Using your examples, this would mean i could use 8 bytes = 16 digits or 16 bytes = 33 digits. Maybe it could fit 24 in 12 bytes - which would be a good combination. That would save 4 bytes per variable. There would still be a hit when accessing variables.

Also, i already have infinities, but no denormalised floats.


#8

Quote:
This would raise the question of whether i should always perform this triple - which would impact performance, or only to pack when i store in variables etc.

The 20b rewrite I'm working on does the latter. The stack and registers are 16 digit packed format and all computations are performed using 39 digits unpacked numbers. Entire computations are performed without packing. Only when the result is known does packing occur.


Quote:
However the variable storage is on the heap, so usually this means sizes are a multiple of 4. Using your examples, this would mean i could use 8 bytes = 16 digits or 16 bytes = 33 digits. Maybe it could fit 24 in 12 bytes - which would be a good combination. That would save 4 bytes per variable. There would still be a hit when accessing variables.

You'd get 25 digits in 12 bytes when packed. Digits are stored three per ten bits.
I don't really see why you'd need 20+ digits except during internal computations though. Even the 16 I'm carrying seems like overkill :-)


- Pauli

#9

Very nice. Now I have to get one.


#10

Hi Egan,

Do you know if hpgcc works with c++ now? last time i looked, version 3 was by request only, so i've lost track of progress.

If so, i could easily make a hp50g port. the 50g is actually a lot more powerful, 2x CPU and a lot more RAM. Also more pixels!

However, i do recommend getting one of these, I find it nicer to carry.


#11

Quote:
Do you know if hpgcc works with c++ now? last time i looked, version 3 was by request only, so i've lost track of progress.

Others have with version 2. The libraries are all C, but you should be able to use any GCC compiler language as long as you can bind to C.

Someone posted to comp.sys.hp48 a Sudoku solver written C++ for HPGCC 2. I think I still have it if you are interested.

#12

Quote:

Do you know if hpgcc works with c++ now? last time i looked, version 3 was by request only, so i've lost track of progress.


Hi Hugh,

I posted the sudoku solver in C++ that Egan referred to. You can get it here: http://www.hpcalc.org/details.php?id=7062

This is a port of a windows program that I wrote.

See glue.cpp for the details of moving between C and C++. You need to implement "new" and "delete" in terms of malloc() and free() (it's easy) and any C++ file that includes the hpgcc header file will need to enclose the #include inside extern "C" { ... }. Finally, it appears that static variables inside functions aren't supported because the static initializer code isn't there.

Dave


#13

Thanks for the Sudoku program reference.

I notice the program has to resort to guesswork (brute force) for some of the hardest puzzles. I had the same problem in my own sudoku solver (which I wrote in lua for the hp50g). I used the methods suggested by Philip Belben from his HPCC datafile articles; “A General Method for Solving Sudoku” V24N6P23 and “More on Solving Sudoku” V25N1P4.

Philip was working on a set of canonical rules that would solve any puzzle. Unfortunately his rules didn’t quite get there, but were interesting nonetheless. To date, I still do not know if there is a (small) set of simple rules to defeat any puzzle.

His rule set was based on 5 increasingly involving rules derived from his experiences solving puzzles manually. When I coded them up I discovered that rule 5 (when generalised) dominated rules 3 & 4. Ie a program with rules 1,2 & 5 solves the same puzzle set as 1,2,3,4,5. So I removed rules 3 & 4 from the implementation. Of course, those rules are still handy for manual solving because they are easier mentally than rule 5.

Then there were the puzzles that were not solved by these rules. In these cases, I found that by guessing a number from a suitable (least unknown) square I would wind up with a solution, stalemate or contradiction. Latter almost always leading to full solution once the original rules are reapplied. Furthermore, I found the puzzle always solvable by one such guess. There were never cases when all guesses to minimum unknown squares failed to reach a solution or contradiction. That being the case meant my guess method did not have to be recursive – which was nice for the calculator memory!

good stuff.


#14

Hi Hugh,

You can find lots of information about solving and generating sudoku here: http://www.setbb.com/phpbb/index.php?mforum=sudoku

Knuth's Dancing Links algorithm can solve any sudoku puzzle. There are lots of different algorithms that can be applied, but after the first half dozen or so, they all look suspiciously like "guess a value and see where it leads" to me.... :)

My solver applies successively more difficult methods to try to make progress on the puzzle, where progress means you can eliminate one or more possible values from a square. If any progress is made, it goes back to the easiest algorithms again. If none of the logical algorithms can solve the puzzle then it applies the one you mention: find a square with the fewest number of possibilities, assume one possibility is correct, and recursively repeat the whole process, starting with the logical algorithms first. Eventually you end up with a solution or an inconsistency, in which case the recursive call exits and you move on to the next possibility for a square. To me, the "guess and see where it leads" method is faster at that point, even for a human.

I haven't checked the number of recursive calls, needed, but doing it by hand with the windows version, I think I've seen a few puzzles that required two levels of recursion.

It was a fun exercise to port the C++ program to the calculator. The solver itself operates in just a few microseconds. All the time needed to run the program comes from the User RPL wrappers that convert from an array to a string and back again.

I think the program is a nice example of the calculator's underlying speed and what can be done in C++.


#15

A few months ago, I wrote a sudoku solver using dumb backtracking (always starting with the entry having the fewest number of possibilities). It solves most newspaper-level sudoku problems in a few milliseconds on my slow computer, and the hardest problem I could find on the web, shown below, takes 0.15 second to solve.

My program reads a single sudoku problem from standard input,
in the following format:

.......12
........3
..23..4..
..18....5
.6..7.8..
.....9...
..85.....
9...4.5..
47...6...

(A dot or the number 0 represents an empty space, and the newlines are optional, so the whole problem could also be entered on an 81-character line.)

Here is the program:

/* Sudoku solver by Paul Guertin <pg@sff.net>, August 2008 */

#include <stdio.h>
#include <string.h>

int neighbor[81][20]; /* lists of all 20 neighbors of each cell 0..80 */
int popcnt[512]; /* count of 1-bits in 0<=i<512 written in binary */
int nbsol, nbcalls;

void init_tables()
/* Initializes the neighbor[][] and popcnt[] tables. */
{
int i, j, p, n[81];

for( p=0; p<81; p++ ) {
memset( n, 0, 81*sizeof(int) );
for( i=0; i<9; i++ )
n[p/9*9+i] = n[p%9+9*i] = n[p/27*27+p/3%3*3+i/3*9+i%3] = 1;
for( i=j=0; i<81; i++ ) {
if( (n[i] == 1) && (i != p) )
neighbor[p][j++] = i;
}
}
for( i=0; i<512; i++ ) {
for( j=popcnt[i]=0; j<9; j++ )
popcnt[i] += (i>>j) & 1;
}
}

void set( int *board, int pos, int val )
/* Puts the value (1..9) in entry pos (0..80) and updates neighbors. */
{
int i;

board[pos] |= val<<9;
for( i=0; i<20; i++ )
board[neighbor[pos][i]] |= 1<<(val-1);
}

int input_board( int *board )
/* Reads a sudoku board from stdin.
Returns 0 if OK, 1 if EOF, -(1..81) if invalid entry found. */
{
int c, n;

n = 0;
memset( board, 0, 81*sizeof(int) );
while( n<81 && (c=getchar()) != EOF ) {
if( c>='1' && c<='9' ) {
if( board[n] & 1 << (c-'1') )
return -n-1;
else
set( board, n++, c-'0' );
}
else if( c == '.' || c == '0' )
n++;
}
return n<81;
}

void print_board( int *board )
/* Pretty-prints a sudoku board to stdout. */
{
int i;

for( i=0; i<81; i++ ) {
if( i==27 || i==54 )
puts( "\n---------+---------+---------" );
else if( !(i%3) )
putchar( i%9 ? '|' : '\n');
printf( " %c ", board[i]>0x200 ? '0'+(board[i]>>9) : '.' );
}
putchar( '\n' );
}

void solve( int *board )
/* Prints all solutions to a sudoku problem. */
{
int i, maxblock, maxpos, keepboard[81];

nbcalls++;
for( i=maxblock=0; i<81; i++ ) {
if( board[i] < 0x200 && popcnt[board[i]] > maxblock ) {
maxpos = i;
maxblock = popcnt[board[maxpos]];
}
}
if( maxblock == 0 ) {
print_board( board );
nbsol++;
}
else if( maxblock < 9 ) {
for( i=0; i<9; i++ ) {
if( !(board[maxpos] & 1<<i) ) {
memcpy( keepboard, board, 81*sizeof(int) );
set( board, maxpos, i+1 );
solve( board );
memcpy( board, keepboard, 81*sizeof(int) );
}
}
}
}

int main()
{
int board[81], error;

/* Each item in the board[] array represents an entry.
The low 9 bits are used to keep track of impossible digits
for that entry (low kth bit is 1 iff digit k+1 is impossible),
and higher bits are used to write a digit in the entry (e.g.,
to set the first entry to 5, use board[0] |= 5<<9). So this
code assumes ints are at least 13 bits. */

init_tables();
if( error = input_board( board ) )
printf( "Illegal input position %d.\n", -error );
else {
print_board( board );
nbsol = nbcalls = 0;
solve( board );
printf( "\n%d solution%s found. ", nbsol, nbsol>1 ? "s" : "" );
printf( "Difficulty level (number of calls): %d\n", nbcalls );
}
return error;
}


#16

Hi Paul,

Thanks for posting your sudoku program. I like it, it’s very short and concise.

Also, your example puzzle is very tough! Has anyone had a go at solving it by hand? I put it into my program and made a discovery – it doesn’t get solved by my, so called, one level guess. So this shows that there are puzzles that need a recursive solve approach.

Because your program is highly recursive, its not suitable for calculators in its current form, but could be adapted. For example, the max depth will be the same as the number of initial unknowns. Eg 64. So we need 63 boards on the stack ~ about 20k. This is a lot for a small stack machine, but not for the heap. Otherwise I think it would work quite well. I also like the fact that it will find all solutions, which is nice to know, in case the puzzle is ambiguous.

Your program demonstrates that trying to translate methods a person would use into a program aren’t always any better than a program that solves by brute force, but in a very streamlined way.

Certainly for this scale of branching factor anyway.


#17

I've tried it on my Casio Z-1GR (8088, C interpreter). Some modifications were (and still are) necessary because:

1) No ANSI prototypes.

2) memset, memcpy are missing.

3) sizeof works on variables only, not on types.

3) The output scrolls off the display.

I plugged in an external power supply and started the program with the hard to solve puzzle as input. I had to enter the numbers manually, there is no input redirection, but at least the solver started.

A few hours later, the solution was on the screen (scrolled off but obviously found). The program was still working, trying to find more solutions. I stopped it...

Memory wasn't a problem, at least on my system with some 40k free RAM, but execution times could be considerably improved by adding a few heuristics.

Here is the modified code:

/* Sudoku solver by Paul Guertin <pg@sff.net>, August 2008 */
/* Casio-C (non ANSI) MvC, Feb 2009 */

/*
#include <stdio.h>
#include <string.h>
*/

int neighbor[81][20]; /* lists of all 20 neighbors of each cell 0..80 */
int popcnt[512]; /* count of 1-bits in 0<=i<512 written in binary */
int nbsol, nbcalls;

memset( buff, val, size )
char *buff;
int val, size;
{
while( size-- ) *buff++ = (char) val;
}

memcpy( dest, src, size )
char *dest, *src;
int size;
{
while( size-- ) *dest++ = *src++;
}

init_tables()
/* Initializes the neighbor[][] and popcnt[] tables. */
{
int i, j, p, n[81];

for( p=0; p<81; p++ ) {
memset( n, 0, 81*sizeof(i) );
for( i=0; i<9; i++ )
n[p/9*9+i] = n[p%9+9*i] = n[p/27*27+p/3%3*3+i/3*9+i%3] = 1;
for( i=j=0; i<81; i++ ) {
if( (n[i] == 1) && (i != p) )
neighbor[p][j++] = i;
}
}
for( i=0; i<512; i++ ) {
for( j=popcnt[i]=0; j<9; j++ )
popcnt[i] += (i>>j) & 1;
}
}

set( board, pos, val )
int *board, pos, val;
/* Puts the value (1..9) in entry pos (0..80) and updates neighbors. */
{
int i;

board[pos] |= val<<9;
for( i=0; i<20; i++ )
board[neighbor[pos][i]] |= 1<<(val-1);
}

int input_board( board )
int *board;
/* Reads a sudoku board from stdin.
Returns 0 if OK, 1 if EOF, -(1..81) if invalid entry found. */
{
int c, n;

n = 0;
memset( board, 0, 81*sizeof(n) );
while( n<81 && (c=getchar()) != EOF ) {
if( c>='1' && c<='9' ) {
if( board[n] & 1 << (c-'1') )
return -n-1;
else
set( board, n++, c-'0' );
}
else if( c == '.' || c == '0' )
n++;
}
return n<81;
}

print_board( board )
int *board;
/* Pretty-prints a sudoku board to stdout. */
{
int i;

for( i=0; i<81; i++ ) {
if( i==27 || i==54 )
puts( "\n---------+---------+---------" );
else if( !(i%3) )
putchar( i%9 ? '|' : '\n');
printf( " %c ", board[i]>0x200 ? '0'+(board[i]>>9) : '.' );
}
putchar( '\n' );
}

solve( board )
int *board;
/* Prints all solutions to a sudoku problem. */
{
int i, maxblock, maxpos, keepboard[81];

nbcalls++;
for( i=maxblock=0; i<81; i++ ) {
if( board[i] < 0x200 && popcnt[board[i]] > maxblock ) {
maxpos = i;
maxblock = popcnt[board[maxpos]];
}
}
if( maxblock == 0 ) {
print_board( board );
nbsol++;
}
else if( maxblock < 9 ) {
for( i=0; i<9; i++ ) {
if( !(board[maxpos] & 1<<i) ) {
memcpy( keepboard, board, 81*sizeof(i) );
set( board, maxpos, i+1 );
solve( board );
memcpy( board, keepboard, 81*sizeof(i) );
}
}
}
}

int main()
{
int board[81], error;

/* Each item in the board[] array represents an entry.
The low 9 bits are used to keep track of impossible digits
for that entry (low kth bit is 1 iff digit k+1 is impossible),
and higher bits are used to write a digit in the entry (e.g.,
to set the first entry to 5, use board[0] |= 5<<9). So this
code assumes ints are at least 13 bits. */

init_tables();
if( error = input_board( board ) )
printf( "Illegal input position %d.\n", -error );
else {
print_board( board );
nbsol = nbcalls = 0;
solve( board );
printf( "\n%d solution%s found. ", nbsol, nbsol>1 ? "s" : "" );
printf( "Difficulty level (number of calls): %d\n", nbcalls );
}
return error;
}

Marcus

#18

Quote:
Because your program is highly recursive, its not suitable for calculators in its current form, but could be adapted. For example, the max depth will be the same as the number of initial unknowns. Eg 64. So we need 63 boards on the stack ~ about 20k. This is a lot for a small stack machine, but not for the heap. Otherwise I think it would work quite well. I also like the fact that it will find all solutions, which is nice to know, in case the puzzle is ambiguous.

One way to shrink the data required is to recognize that you don't need to store the entire board when you recurse. Instead you can store the value of the square that you're currently guessing, along with the values of it's 20 neighbors. That's because these are the only things that change when you set the value of the square.

A further optimization would be to recognize that you're only changing one bit of the neighbors, so you can store the previous value of the current square, plus a bit for each of the 20 neighbors.

#19

Quote:
Also, your example puzzle is very tough! Has anyone had a go at solving it by hand? I put it into my program and made a discovery – it doesn’t get solved by my, so called, one level guess. So this shows that there are puzzles that need a recursive solve approach.


I entered it into Wayne Gould's Sudoku program and it said it was not a valid puzzle. The message included a note that about 1 in 700 puzzles printed in books and magazines are actaully impossible.

I then entered it into Angus Johnson's "Simple Sudoku" and it only got one step before it was stumped.

Both these programs use methods a human solver would go through. This puzzle may only be solvable by brute-force-trial-and-error.

#20

Quote:
Because your program is highly recursive, its not suitable for calculators in its current form, but could be adapted.

David Hayden pointed out some possible optimizations that can save much memory. There is also an easy way to drastically cut the recursion depth:

For the sake of simplicity, the function solve() recurses even when there is only one possibility for a missing digit (i.e. when the variable maxblock is equal to 8). It is a simple matter to add a few lines of code so that it doesn't recurse until maxblock is less than 8. When I tried it, the maximum depth of recursive calls for the tough problem went from 63 to 24, and most newspaper-level problems seem to require a depth around 5.

#21

Hi Hugh,

nice application. I've received my machine just yesterday, went to the edu.casio.com download site, logged in and tried to get the SDK. Somehow I do not qualify for the download. :( What are the steps to take for a developer to get the necessary tools?

Another question to the public: Would the Casio qualify as a free42 platform?


#22

Hi Marcus,

You have to type in the numbers from the back of the unit to download the SDK. It's a bit silly i know.

I'm not really sure whether this is to validate you are a true owner or just some kind of data collection idea.

If it's not some kind of license restriction, it would be an excellent way for people here to try stuff out. The SDK comes with an emulator which can run apps under windows.


#23

Thanks, that worked for me. Is your app downloadable ?


#24

Soon will be. I'm going to release a public version in about a week or so. I have a list of minor wibbles to fix first.

Then i'll just try it out for a bit first, trying to head off that embarassing bug (that always gets out there) before the release.

:-)


Possibly Related Threads...
Thread Author Replies Views Last Post
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 402 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  ENG button (like Casio calculators) on HP Prime uklo 3 276 11-04-2013, 09:45 PM
Last Post: LHH
  HP Prime Program: Sampling Without Replacement Eddie W. Shore 13 566 10-04-2013, 12:22 AM
Last Post: Joe Horn
  HP48GX screen replacement Francisco Quiles 9 497 10-03-2013, 09:17 PM
Last Post: Francisco Quiles
  HP 2225D+ RAM failure/replacement Luca 4 322 09-10-2013, 01:46 PM
Last Post: Luca
  [HP Prime] Request: re-execute history like CASIO classPAD serie 300/400 CompSystems 1 212 09-03-2013, 02:47 PM
Last Post: CompSystems
  HP 15C-LE replacement still available? Borja 16 779 08-22-2013, 11:16 AM
Last Post: Michael de Estrada
  OT: Does anyone have the new Casio Classpad fx-CP400? Eddie W. Shore 4 290 08-20-2013, 08:42 AM
Last Post: Eddie W. Shore
  Battery replacement HP75C Chris H (UK) 1 183 08-05-2013, 11:02 AM
Last Post: Sylvain Cote
  Another non-HP RPN vintage calculator joins the collection Michael de Estrada 2 310 07-23-2013, 04:10 PM
Last Post: Walter B

Forum Jump: