Tag: Computer Science
Blog Entry © Sunday, November 30, 2025, by James Pate Williams, Jr. and the Microsoft Artificially Intelligent Agent, the Copilot
Blog Entry © Saturday, November 28, 2025, by James Pate Williams, Jr. Fair Coin and Fair Dice Probabilities
Blog Entry © Tuesday 25, 2025, by James Pate Williams, Jr. Enumeration of the Tic-Tac-Toe Game Tree
/*
* Board.h
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Modified on Monday 11/24/2025
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#ifndef _Board_
#define _Board_
#include <fstream>
#include <vector>
class Board {
private:
char state[9];
std::vector<std::vector<char>> board;
public:
Board(void);
Board(const Board &board);
Board(const char b[3][3]);
Board(const std::vector<char> &v);
char GetState(int n) const;
void PrintBoard(int n) const;
void WriteBoard(std::ofstream &out) const;
friend bool operator == (const Board &b1, const Board &b2);
friend bool operator != (const Board &b1, const Board &b2);
friend bool Found(const Board &initial, const Board &board);
friend bool Win(const Board b, char winner[8]);
friend bool LegalBoard(
bool& legal, bool& won, char& whoWon, const Board b);
friend void PrintBoard(char board[3][3], int number);
static const char CharX, CharO, CharS;
};
#endif
/*
* Board.cpp
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>
#include "Board.h"
const char Board::CharO = 'o';
const char Board::CharX = 'x';
const char Board::CharS = '_';
Board::Board(void) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 9; i++)
state[i] = '\0';
}
Board::Board(const Board &b) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b.state[3 * i + j];
}
Board::Board(const char b[3][3]) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b[i][j];
}
Board::Board(const std::vector<char> &v) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = v[3LL * i + j];
}
char Board::GetState(int n) const {
return state[n];
}
void Board::PrintBoard(int n) const {
std::cout << n << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << state[3 * i + j];
std::cout << std::endl;
}
std::cout << std::endl;
std::cout << std::endl;
}
void Board::WriteBoard(std::ofstream &out) const {
for (int i = 0; i < 9; i++)
out << state[i];
out << std::endl;
}
bool operator == (const Board &b1, const Board &b2) {
int i, equal = 0;
for (i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
equal++;
return equal == 9;
}
bool operator != (const Board &b1, const Board &b2) {
for (int i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
return false;
return true;
}
bool Found(const Board &initial, const Board &board) {
// reflections
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[3] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[5] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[1] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[7] &&
initial.state[8] == board.state[6])
return true;
if (initial.state[0] == board.state[0] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[8])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[2] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[6] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[0])
return true;
// rotations
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[0])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[6])
return true;
// equal
return initial == board;
}
bool Win(const Board b, char winner[8]) {
bool win = false;
for (int i = 0; i < 8; i++)
winner[i] = Board::CharS;
if (b.board[0][0] == b.board[0][1] && b.board[0][0] ==
b.board[0][2] && b.board[0][0] != Board::CharS) {
winner[0] = b.board[0][0];
win = true;
}
if (b.board[1][0] == b.board[1][1] && b.board[1][0] ==
b.board[1][2] && b.board[1][0] != Board::CharS) {
winner[1] = b.board[1][0];
win = true;
}
if (b.board[2][0] == b.board[2][1] && b.board[2][0] ==
b.board[2][2] && b.board[2][0] != Board::CharS) {
winner[2] = b.board[2][0];
win = true;
}
if (b.board[0][0] == b.board[1][0] && b.board[0][0] ==
b.board[2][0] && b.board[0][0] != Board::CharS) {
winner[3] = b.board[0][0];
win = true;
}
if (b.board[0][1] == b.board[1][1] && b.board[0][1] ==
b.board[2][1] && b.board[0][1] != Board::CharS) {
winner[4] = b.board[0][1];
win = true;
}
if (b.board[0][2] == b.board[1][2] && b.board[0][2] ==
b.board[2][2] && b.board[0][2] != Board::CharS) {
winner[5] = b.board[0][2];
win = true;
}
if (b.board[0][0] == b.board[1][1] && b.board[0][0] ==
b.board[2][2] && b.board[0][0] != Board::CharS) {
winner[6] = b.board[0][0];
win = true;
}
if (b.board[0][2] == b.board[1][1] && b.board[0][2] ==
b.board[2][0] && b.board[0][2] != Board::CharS) {
winner[7] = b.board[0][2];
win = true;
}
return win;
}
void PrintBoard(char board[3][3], int number) {
std::cout << "number = " << number << std::endl;
std::cout << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << board[i][j];
std:: cout << std::endl;
}
std::cout << std::endl;
}
bool LegalBoard(
bool &legal, bool &won, char &whoWon, const Board b) {
bool winO, winX;
char winner[8];
int countO = 0, countS = 0, countX = 0;
int i, j, oWins = 0, xWins = 0;
legal = won = false;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (b.board[i][j] == Board::CharO)
countO++;
else if (b.board[i][j] == Board::CharX)
countX++;
else if (b.board[i][j] == Board::CharS)
countS++;
}
}
if ((countX >= 3 || countO >= 3) && Win(b, winner)) {
for (i = 0; i < 8; i++) {
if (winner[i] == Board::CharX)
xWins++;
else if (winner[i] == Board::CharO)
oWins++;
}
winX = (xWins >= 1 && oWins == 0) &&
(countX <= 5 && countO <= 4 && countX == countO + 1);
winO = (xWins == 0 && oWins >= 1) &&
(countO <= 5 && countX <= 4 && countO == countX + 1);
legal = won = winX || winO;
if (won && winX)
whoWon = Board::CharX;
else if (won && winO)
whoWon = Board::CharO;
}
else
legal = (countX <= 5 && countO <= 4 && countX == countO + 1) ||
(countO <= 5 && countX <= 4 && countO == countX + 1);
return legal;
}
#define _WriteBV_
#include <algorithm>
#ifdef _WriteBV_
#include <fstream>
#endif
#include <iomanip>
#include <iostream>
#include <vector>
#include "Board.h"
static int Compare(const void *vPtr1, const void *vPtr2) {
char *cPtr1 = (char *) vPtr1;
char *cPtr2 = (char *) vPtr2;
return strcmp(cPtr1, cPtr2);
}
static void EnumerateTicTacToe(void) {
bool legal, won;
char b[3][3], whoWon;
char tree[3][3][3][3][3][3][3][3][3];
int i0, i1, i2, i3, i4, i5, i6, i7, i8;
int legals = 0, number = 0, wCount = 0;
int xCount = 0, oCount = 0;
int bvSize, i, j;
std::vector<Board> boardVector;
for (i0 = 0; i0 < 3; i0++) {
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
for (i3 = 0; i3 < 3; i3++) {
for (i4 = 0; i4 < 3; i4++) {
for (i5 = 0; i5 < 3; i5++) {
for (i6 = 0; i6 < 3; i6++) {
for (i7 = 0; i7 < 3; i7++) {
for (i8 = 0; i8 < 3; i8++) {
if (i0 == 0)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i0 == 1)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i0 == 2)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i1 == 0)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i1 == 1)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i1 == 2)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i2 == 0)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i2 == 1)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i2 == 2)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i3 == 0)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i3 == 1)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i3 == 2)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i4 == 0)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i4 == 1)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i4 == 2)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i5 == 0)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i5 == 1)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i5 == 2)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i6 == 0)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i6 == 1)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i6 == 2)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i7 == 0)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i7 == 1)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i7 == 2)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i8 == 0)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i8 == 1)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i8 == 2)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
Board bb(b);
if (LegalBoard(legal, won, whoWon, bb)) {
Board board(b);
legals++;
if (won) {
wCount++;
if (whoWon == Board::CharX)
xCount++;
else if (whoWon == Board::CharO)
oCount++;
}
boardVector.push_back(board);
}
number++;
}}}}}}}}}
for (i = 0; i < boardVector.size() - 1; i++)
for (j = i; j < boardVector.size(); j++)
if (Found(boardVector[i], boardVector[j]))
boardVector.erase(boardVector.begin() + j);
bvSize = (int)boardVector.size();
std::cout << std::setw(4) << "legal total = " << legals << std::endl;
std::cout << std::setw(4) << "xWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oxWin total = " << xCount + oCount << std::endl;
std::cout << std::setw(4) << "unique size = " << boardVector.size();
std::cout << std::endl;
#ifdef _WriteBV_
std::cout << std::endl;
std::ofstream outFile("Tic TacToe Game Tree Enumeration.txt");
std::cout << std::endl;
for (i = 0; i < bvSize; i++) {
boardVector[i].PrintBoard(i + 1);
boardVector[i].WriteBoard(outFile);
}
#endif
}
int main (int argc, char * const argv[]) {
EnumerateTicTacToe();
return 0;
}
Blog Entry © Monday, November 24, 2025, by James Pate Williams, Jr., A* Informed Search Application to Solve the 15-Tile Puzzle
Blog Entry © Sunday, November 23, 2025, by James Pate Williams, Jr. Modification of My A* Informed Search Solver for the 8-Tile Puzzle
Blog Entry © Friday, November 21, 2025, by James Pate Williams, Jr., Win32 C/C++ Desktop GUI Solution of the 15-Tile Puzzle Using Iterative Deepening A* Informed Seach Algorithm
Blog Entry © Monday, November 17, 2025, by James Pate Williams, Jr. An Elitist Evolutionary Hill Climber to Solve the 8-Tile Puzzle
Blog Entry © Sunday, July 27, 2025, A Bit of Programming Nostalgia Prime Number Related Programs by James Williams, Jr.
/*
Author: Pate Williams c 1995
The following program is a solution to problem 18.15
in Pascalgorithms by Edwin D. Reilly and Francis D.
Federighi page 627. The program uses Simpson's rule
to calculate the number of primes less than or equal
a given number.
*/
#include <math.h>
#include <stdio.h>
typedef double real;
static real f(real x)
{
return(1.0 / log(x));
}
static real simpson(int n, real a, real b)
{
int i;
real evensum, h, oddsum, twoh, x;
if (n % 2 == 1) n = n - 1;
h = (b - a) / n;
twoh = h + h;
x = h + a;
oddsum = 0.0;
for (i = 1; i <= n / 2; i++)
{
oddsum += f(x);
x = twoh + x;
}
x = twoh + a;
evensum = 0.0;
for (i = 1; i <= n / 2 - 1; i++)
{
evensum += f(x);
x = twoh + x;
}
return(h / 3.0 * (f(a) + f(b) + 4.0 * oddsum + 2.0 * evensum));
}
int main(void)
{
int i, n, Nmaximum = 0, Nminimum = 0, Nstep;
printf("n = "); scanf_s("%d", &n);
printf("N minimum = "); scanf_s("%d", &Nminimum);
printf("N maximum = "); scanf_s("%d", &Nmaximum);
printf("N step = "); scanf_s("%d", &Nstep);
printf("\n");
printf("----------------------------------------\n");
printf("Min\t\tMax\t\tprimes\n");
printf("----------------------------------------\n");
for (i = Nminimum; i <= Nmaximum; i += Nstep)
{
printf("%8d\t%8d\t%8.0lf\n", Nminimum, i + Nstep,
simpson(n, Nminimum, i + Nstep));
}
printf("----------------------------------------\n");
return(0);
}
n = 1024
N minimum = 0
N maximum = 10000000
N step = 1000000
----------------------------------------
Min Max primes
----------------------------------------
0 1000000 78551
0 2000000 148923
0 3000000 216788
0 4000000 283122
0 5000000 348361
0 6000000 412754
0 7000000 476461
0 8000000 539590
0 9000000 602224
0 10000000 664424
0 11000000 726239
----------------------------------------
D:\PrimeCounter\x64\Release\PrimeCounter.exe (process 51884) exited with code 0 (0x0).
Press any key to close this window . . .
/*
Author: Pate Williams c 1995
The following is a translation of the Pascal program
sieve found in Pascalgorithms by Edwin D. Reilly and
Francis D. Federighi page 652. This program uses sets
to represent the sieve (see C Programming Language An
Applied Perspective by Lawrence Miller and Alec Qui-
lici pages 160 - 162).
*/
#include <math.h>
#include <stdio.h>
#define _WORD_SIZE 32
#define _VECT_SIZE 524288
#define SET_MIN 0
#define SET_MAX 16777215
typedef unsigned long SET[_VECT_SIZE];
typedef long ELEMENT;
typedef unsigned long LONG;
SET set;
static int get_bit_pos(int* long_ptr, int* bit_ptr,
ELEMENT element)
{
*long_ptr = element / _WORD_SIZE;
*bit_ptr = element % _WORD_SIZE;
return(element >= SET_MIN && element <= SET_MAX);
}
static void set_bit(ELEMENT element, int inset)
{
int bit, word;
if (get_bit_pos(&word, &bit, element))
{
if (inset > 0)
set[word] |= (01 << bit);
else
set[word] &= ~(01 << bit);
}
}
static int get_bit(ELEMENT element)
{
int bit, word;
return(get_bit_pos(&word, &bit, element) ?
(set[word] >> bit) & 01 : 0);
}
static void set_Add(ELEMENT element)
{
set_bit(element, 1);
}
static void set_Del(ELEMENT element)
{
set_bit(element, 0);
}
static int set_Mem(ELEMENT element)
{
return get_bit(element);
}
static void primes(long n)
{
long c, i, inc, k;
double x;
set_Add(2);
for (i = 3; i <= n; i++)
if ((i + 1) % 2 == 0)
set_Add(i);
else
set_Del(i);
c = 3;
do
{
i = c * c;
inc = c + c;
while (i <= n)
{
set_Del(i);
i = i + inc;
}
c += 2;
while (set_Mem(c) == 0) c += 1;
} while (c * c <= n);
k = 0;
for (i = 2; i <= n; i++)
if (set_Mem(i) == 1) k++;
x = n / log(n) - 5.0;
x = x + exp(1.0 + 0.15 * log(n) * sqrt(log(n)));
printf("%8ld\t%8ld\t%8.0lf\n", n, k, x);
}
int main(void)
{
long n = 100L;
printf("----------------------------------------\n");
printf("n\t\tprimes\t\ttheory\n");
printf("----------------------------------------\n");
do
{
primes((int)n);
n = 10L * n;
} while (n < (long)SET_MAX);
printf("----------------------------------------\n");
return(0);
}
----------------------------------------
n primes theory
----------------------------------------
100 25 29
1000 168 181
10000 1229 1261
100000 9592 9634
1000000 78498 78396
10000000 664579 665060
----------------------------------------
D:\Sieve\x64\Release\Sieve.exe (process 60092) exited with code 0 (0x0).
Press any key to close this window . . .
Rice-Golomb Encoder and Decoder Copyright (c) Thursday, April 3, 2025, to Sunday, April 6, 2025, by James Pate Williams, Jr. BA, BS, Master of Software Engineering, Doctor of Philosophy Computer Science
Online references:
https://en.wikipedia.org/wiki/Golomb_coding
// Rice-Golomb Encoder and Decoder
// Copyright (c) Thursday, April 3, 2025
// by James Pate Williams, Jr.
// BA, BS, Master of Software Engineering
// Doctor of Philosophy Computer Science
// Online references:
// https://en.wikipedia.org/wiki/Golomb_coding
// https://ntrs.nasa.gov/api/citations/19790014634/downloads/19790014634.pdf
#include <iostream>
#include <string>
#include <vector>
//#include <stdlib.h>
bool Encode(const char* NChars, size_t NCharsCount,
long M, long long& N, std::vector<char>& qBits,
std::vector<char>& rBits, unsigned int& qSize, unsigned int& rSize,
long long& q, long long& r, unsigned int& NSize) {
N = NChars[0] - (long long)'0';
for (unsigned int i = 1; i < NCharsCount; i++) {
N = 10 * N + (long long)NChars[i] - (long long)'0';
}
q = N / M;
r = N % M;
qSize = 0;
while (qSize < q) {
qBits.push_back('1');
qSize++;
}
qBits.push_back('0');
qSize++;
rSize = 0;
unsigned int b = (unsigned int)floor(log2(M));
if (b > 62) {
return false;
}
long long p = (long long)pow(2, b + 1);
if (r < p - M) {
long long rr = r;
while (rr > 0) {
long long digit = (rr & 1) == 1 ? 1 : 0;
rBits.push_back((char)digit + '0');
rSize++;
rr >>= 1;
}
rBits.push_back('0');
rSize++;
}
else {
long long rr = r + p - M;
while (rSize < b + 1) {
long long digit = rr & 1 ? 1 : 0;
rBits.push_back((char)digit + '0');
rSize++;
rr >>= 1;
}
}
long long rValue = rBits[0];
for (size_t i = 1; i < rSize; i++) {
rValue = rValue * 2 + rBits[i];
}
long long NBitCount = 0;
while (N > 0) {
N >>= 1;
NBitCount++;
}
std::cout << "q-bits size = " << qSize << std::endl;
std::cout << "r-bits size = " << rSize << std::endl;
std::cout << "N-bits size = " << qSize + rSize << std::endl;
std::cout << "N-Chars * 8-Bits per Char = " << NCharsCount * 8 << std::endl;
std::cout << "% Compression = " << 100.0 * (1.0 - (qSize + rSize) /
(NCharsCount * 8.0)) << std::endl;
return true;
}
void Decode(long long M, long long& N,
std::vector<char> qBits, std::vector<char> rBits,
unsigned int& qSize, unsigned int& rSize,
long long& q, long long& r) {
int count = 0;
while (qBits[count] != '0') {
count++;
}
q = count;
int c = (int)rSize - 1;
unsigned int b = (unsigned int)floor(log2(M));
long long p = (long long)pow(2, b + 1);
long long s = 0;
r = rBits[c--] - (long long)'0';
do {
r = 2 * r + rBits[c] - (long long)'0';
c--;
} while (c >= 0);
if (r < p - M) {
s = r;
}
else {
s = r + p - M;
c = 1;
r = rBits[0] - (long long)'0';
while (c < (int)(b + 1)) {
r = 2 * r + rBits[c] - (long long)'0';
c++;
}
s = r;
}
r = s;
N = q * M + r;
}
int main() {
char line[128] = { };
size_t NSize = 0, qSize = 0, rSize = 0;
long long M = 10, N = 42, q = -1, r = -1;
std::vector<char> qBits, rBits;
std::cout << "M = ";
std::cin.getline(line, 127);
std::string str1(line);
M = std::stoi(str1);
std::cout << "N = ";
std::cin.getline(line, 127);
std::string str2(line);
Encode(str2.c_str(), strlen(str2.c_str()), M, N,
qBits, rBits, qSize, rSize, q, r, NSize);
std::cout << "q = " << q << std::endl;
std::cout << "r = " << r << std::endl;
std::cout << "q-size = " << qSize << std::endl;
std::cout << "r-size = " << rSize << std::endl;
std::cout << "q ";
for (unsigned int i = 0; i < qSize; i++) {
std::cout << qBits[i] << ' ';
}
std::cout << std::endl;
std::cout << "r ";
for (int i = (int)rSize - 1; i >= 0; i--) {
std::cout << rBits[i] << ' ';
}
std::cout << std::endl;
Decode(M, N, qBits, rBits, qSize, rSize, q, r);
std::cout << "q = " << q << std::endl;
std::cout << "r = " << r << std::endl;
std::cout << "q-size = " << qSize << std::endl;
std::cout << "r-size = " << rSize << std::endl;
std::cout << "q ";
for (unsigned int i = 0; i < qSize; i++) {
std::cout << qBits[i] << ' ';
}
std::cout << std::endl;
std::cout << "r ";
for (int i = rSize - 1; i >= 0; i--) {
std::cout << rBits[i] << ' ';
}
std::cout << std::endl;
std::cout << "N = " << N << std::endl;
return 0;
}
M = 64
N = 1027
q-bits size = 17
r-bits size = 3
N-bits size = 20
N-Chars * 8-Bits per Char = 32
% Compression = 37.5
q = 16
r = 3
q-size = 17
r-size = 3
q 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
r 0 1 1
q = 16
r = 3
q-size = 17
r-size = 3
q 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
r 0 1 1
N = 1027
Numerical Explorations 