Basic,Advanced,Power of 2, Super Advanced, Slotting Distributing problem

3 views
Skip to first unread message

Skybuck Flying

unread,
Jun 6, 2022, 12:00:16 PMJun 6
to
A. Basic Slotting Distributing problem:

1. Given a number of "total slots" (can also be described as output slots)

2. Given a number of "input numbers"

3. Distribute the "input numbers" over the "total slots" such that the "number of intermediate slots" is the same.

(It'd be helpfull to also mention the number of intermediate ranges. This will always be "input numbers-1". (Input numbers<=1 is invalid)

B. Advanced Slotting Distributing problem:

4. It is allowed to calculate "total slots" as a multiplicative of "input numbers", (do specify the multiplier)

For example: Total Slots = "Input Numbers" x2 or x3 or x4 ox 5
So for example Total Slots = (Inputs Numbers x 3)
Multiplier = 3

C. Advanced Power of 2 Slotting Distributing problem:

5. Total Slots must be a power of 2.

D. Super Advanced Power of 2 Slotting Distributing problem;

6. Input numbers must be a power of 2.

In all situations, the total ammount of slots should all be used. In such a solution is not available, then nearest fit could still be interesting.
But for now only solutions that use all slots and meet all other constraints are to be considered valid and interesting solutions.
Especially because these solutions use their "input bits" and "output bits" for input numbers and total numbers efficiently in the case
of "super advanced power of 2 slotting problem and solutions".

To describe the solutions it's usefull to also specify the multiplier that was used to multiple the number of input slots to produce the number of output/total slots.

Which combinations of input, total slots and intermediate numbers are possible ?

Is/are there formulas that can help with this ?

So examples of valid solutions:

Input Numbers = 2 (0 to 1)
Intermediate ranges = 1 (2-1=1)
Total Slots = 32 (0 to 31)
Intermediate Slots = 30 ( 1 to 30)
Multiplier = 16

This simple solution meets all criteria for D
Input numbers is power of 2
Total slots is power of 2
All slots are used.
Intermediate slots is equal (only one set)

Other random example:

Input number = 8 ( 0, 1, 2, 3, 4, 5, 6, 7)
Intermediate ranges = (8-1=7)
Multiplier = 4
Total slots = 32
Intermediate slots = 32-8=26/7 = 3,714 = 3 (inperfect fit) 3x7 = 21
Invalid solution.
Total slots used would be: 21+8 = 29 (best inexact fit)

For now I intend to brute force this problem, to find any solutions that way, but it would be interesting to have some math people look
at this, maybe they can find some formulas that can help with finding perfect solutions.

Practical application for this is:

Scale VGA palette to a larger Palette.

Classic VGA palette has 64 input colors.
Modern VGA palette has 256 input colors.

Goal is to find a new VGA palette with more input colors, say 512, 1024, 2048, 4096, 8192.

For now it's interesting to look at "rows" of 16 input colors.

So scaling 16 input colors to:
32,64,128,256,512,1024,2048,4096,8192, and so on.

Is there a combination where there is a perfect fit for intermediates and totals and such as described above ? where multiplier is also an integer, preferably also a power of 2 for shifting purposes.
(Shifting faster than multiplications and divisions and should therefore allow real-time computation to convert from input to output or vice versa, a few other instructions consuming 1 or 2 clock cycles would be allowable as well, like addition and subtraction)

All variables should be at least integer for valid solutions.

Bye for now,
Skybuck.

Skybuck Flying

unread,
Jun 6, 2022, 6:47:45 PMJun 6
to
I have come to the conclusion that the "redistributing/intermediate insertion (for interpolation) problem" is a little bit more complex than in this problem description so far.

But the problem description is still usefull per dimension.

However currently the VGA palette is split into 16 rows of 16 shades.

Each row is it's own dimension.

For example
Dimension 0: shade 0 to 15
Dimension 1: shade 16 to 31
Dimension 2: shade 32 to 47

I do not want to shade/interpolate/insert between 15 and 16. So these dimensions are not inside a single scalable linear dimension.

Simply multiplieing or shifting these indexes would create "empty additional space" between 15 and 16, basically wasted space/slots.

Bye for now,
Skybuck.
Reply all
Reply to author
Forward
0 new messages