Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Regarding Diablo II. Diablo II - The Lord of Destruction patches starting from 1.14 versions, support with windows xp is deprecated. So you can't run it in PCem because it doesn't support Windows 7 and anything above. Nevertheless, 14 version under the hood doesn't have any drastic changes. This means, atm you can TAS versions from 1.0 to 1.13d of Diablo II LoD. You can't TAS Diablo 2 Resurrected because it require modern graphics support, and we don't have a way atm to run it in PCem.
What it means? Well, it means no those new Diablo 2 Resurrected strats available. So, you need to refer to speedruns of classic LoD or plain Diablo II. And I doubt it's possible to finish the game faster than 30 minutes there. And yes, routing is very complicated. You can use basic route of RTA, but I think they would be suboptimal, because they don't use advantages of TAS.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
I want to say, that this game works in PCem with https://tasvideos.org/EmulatorResources/PCem/Windows setup win xp sp3
Here it is with Pentium II 450MHz. Lags, even though on official site it should be enough. May be voodoo graphics card is somehow making it slow? I don't know. It's just testing, so obviously suboptimal.
Link to video
And here is with overclocked Pentium II 2000MHz:
Link to video
Looks like it's full speed, but I didn't hack the game to verify it's true 100% speed.
Downside of TASing it in PCem for me is: it runs at 8-10 fps on my laptop (the only pc I have) because it's very old. Also, After recording video I tried to make savestate, and it just crashed.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Definite yes from me.
Sadly, only a few days ago we got new understanding of how levels work. I think, it's possible to shave some extra frames using new information.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Here is Lua script for parsing level scripts. https://gist.github.com/realmonster/9c4325aa0d2fa825549abe7675e3e0c2
It was tested in Gens. For bizhawk you need only change shortcuts. Run it once in any level.
Description of output:
There are following two types of lines within the output. Camera-related trigger.
enemy x=12E y=B5 hb=0 code=20504
this tells us that when Camera in position "good" for x = 12E and y = B5, then it will spawn enemy with those parameters, and its "code" is 20504. Code defines what enemy is spawned, and its behavior. What means Camera in "good" position? It depends on "direction" of level. If you walk or fly to the right, then it checks x position, if you move or fly to up, then it check y position. It triggers when the coordinate falls within certain range. Range width is fixed both for horizontal and vertical levels. And coordinate of trigger gives offset of this range.
action x=1E0 y=0 code=1693A
Similarly, when Camera is in "good" position, then action is started. I call it at this moment "action" because it's similar to an "act" in theater, a part of a play in the theater.
unknown offs=16118 x=801 y=112 hb=0 code=1FF78
This means that my script unable identify what trigger does, but its real code is at offset 1FF78. You can disassemble it and look what it is. Similarly with other Camera-related triggers, it's only triggered when Camera in "good" position.
Other part of output is disassemble of actions code. It starts with:
======= action 1693A =======
it tells entry point of action.
Then code of action is listed until line
===========
Each line is in format: offset command
For example:
16946: set_timer F00
It means that at offset 16946 (hex) there is command set_timer with operand F00.
A little note about commands names. It's my naming, of course I have no idea about original naming.
Basic commands:
lock_screen - locks screen
unlock_screen - unlocks screen
set_enemy_limits - sets enemy limits which required to make this action active
set c1 - sets action own variable c1 to the value. it's used to make simple loops in conjunction with dbf.
set c2 - sets action own variable c2 to the value. it's used to make simple loops in conjunction with dbf.
exec - its single argument is offset of raw m68k code. you can disassemble it.
Control flow:
set_timer - set timer and postpone execution.
set_timer rand[ ) - set timer to a random value within range in the brackets. Brackets means low is inclusive, and high is not inclusive.
spawn - spawns something and postpone execution. Most of occurrences it's enemy. But I'm not sure if it's always enemy. See format of enemy description below.
spawn_multiple - spawns multiple enemies simultaneously, and postpone execution.
spawn_random - spawns one enemy from the list, and postpone execution.
wait_enemies - postpone execution until enemies less than or equal the number.
jmp - jump action execution to the offset
jmprnd - jump action execution to one from the list
dbf - two operands: counter and offset. Decrease counter and jump to the offset, but only if it was positive before. So if set c1 = 5, and then dbf c1, it means the number of repetition is 5.
die - terminate action, no mater when
jsr - jump to subroutine
rts - return back from subroutine
There is also several unknown commands. All of their names starts from "unknown".
Spawn description. there are four numbers in square brackets. First two is X and Y position. If brackets are round, then it's position relative to camera. If brackets are square, then it's global position. Third number is some parameter of enemy. I don't know at this moment. And the last number is offset to enemy code. Its code is not m68k raw code. It's in similar fashion as scripts of actions, but with some differences.
Important note about action execution. It is inactive if its timer value > 0, and if enemies count >= numbers in its parameters. In feos script in the video above. those 5, 5 numbers or 7FFF and 7FFF it's restriction for script being active. If enemies count (2 bytes value at offset FFDFAA) is high enough, script doesn't do anything. Literally. First of those two numbers is limit if one player alive, and second if two players alive. So, for example, action has numbers 3, 4 and one character alive, then it's require 2 or less enemies to be alive to even reduce timer of action. If other player press start to revive character, then it require 3 or less enemies to be alive. So, if 3 enemies were alive and timer was 0 at the moment when other player pressed start to revive character, then action will continue execution on the next frame, but it won't continue if other player won't press start.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Dimon12321 wrote:
Looks cool, although its entertainment value is questionable at a distance.
Thanks. Yes, I understand. Taking into account it has 42 levels it will take several hours of gameplay which throws it directly into Vault category I guess.
Dimon12321 wrote:
BTW, is such a TAS acceptable, if you explicitly modify the RAM?
I didn't care. It's the only justifiable goal which I've found for myself. Others seems not interesting for me.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Link to video
There are some other short tests in video description.
1) It runs fine in libTAS and sync perfectly
2) I made Lua script for display of various info
First thing to mention: score and cash just the same thing in the game.
Also, more cash you get, more DPS you have, faster you may kill bosses, as a bonus you'll kill mobs faster too.
Everything else is autoscrolling.
So killing mobs as much as possible happens to be way to get run shorter.
There is also random gold drop from enemies. which also give opportunity to get better weapon...
After those few tests, including heavy rng manipulation to get best cash drop, it turns out:
1) Making gold drop is not fun experience for me, increasing time spent a lot.
2) Bonus it gives is kinda overpowered. After two levels on Hard you have enough cash to pretty much insta-kill every enemy. If you continue like that, you'll insta-kill everything for almost whole the game (because the game has 42 levels)
Those two points convince me that I should not manipulate gold drop, and even more, I should manipulate that random gold drop would not happen.
Issue with farming cash from killing enemies gives less time to play-around, and may lead TAS to be boring.
Anyway, I thought because how hell long game is, I decided to use hardest available difficulty: Impossible (only via RAM overwrite),
And check how far it's manageable to walk through.
But then, I lost motivation after one and half level.
Because how hard is actually TAS it, and how much time I've spent on it. (I think more than 20 hours).
Edit: (11 Dec 2023)
Movie file: https://tasvideos.org/UserFiles/Info/638378342113617178
RAM Watches: https://tasvideos.org/UserFiles/Info/638378343480175111
Lua overlay: https://tasvideos.org/UserFiles/Info/638378346692955946
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
OmnipotentEntity wrote:
I would be interested to know as well, r57shell. I played around for a very short time with it, and it seemed complicated to me.
Here is a proof for pizza question. By the way, I didn't know proof before hand, I asked here in case someone knew / could find a proof. So, here is at least some proof.
https://www.youtube.com/watch?v=h0YHMOkKsy4 check out my comment to this video for additional details (if it's still there)Bobo the King wrote:
As part of attempting the Riddler Classic, I broke things down into a four dimensional region in which 0<w<x<y<z<1. (You can sort of see why I would want to do this, with w, x, y, and z being the four teams in increasing order of quality.) Like your typical mere mortal, I'm no good at visualizing things in four dimensions so I decided to draw the corresponding problem for three dimensions: 0<x<y<z<1. This volume is a tetrahedron embedded within the unit cube. With a little reasoning, you can determine the edges of this tetrahedron:
Main problem for this task is... cost function. You can't just take a volume, because it's not what asked. What asked is quality of champion on average. And for chosen tuple of (a,b,c,d) with properties a<=b<=c<=d, it's already complete mess! I don't know how to simplify it.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
There is an old question, which is easy to guess, but I have no idea how to prove. Perhaps there are some experts who can prove it.
Suppose you have a pizza. And there are two possibilities: you'll have party of N people or party of M people. (including yourself).
In what minimum number of slices (pieces) you need to cut this pizza, such that in both possibilities each member will able to get same amount of pizza without making additional cuts, and there will be no remaining slices (pieces) in both cases. Slices can be any size.
For example, N = 2, M = 3, answer is 4.
I'm interested in proof!
Edit: in one nice discord server one guy sent me link to a proof on youtube (: So I have a proof! Yay!
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
jeff_town wrote:
I noticed that pieces would spawn even if some of the four positions they occupy are already filled. This seems different than the 'best' technical description (https://meatfighter.com/nintendotetrisai/#Spawning_Tetriminos) I found in a few minutes searching, which (sadly, without calling out the code that implements it) describes the algorithm as follows:
In fact, normally, we think of game over as when the pile reaches the top. But, this is not entirely correct. The game actually ends when it is no longer possible to spawn the next piece. That is, all four cells of the playfield corresponding to the spawned Tetrimino's square positions must be empty before the piece can be introduced.
Rather, it looks like the piece is successfully spawning when a single square is empty. Is that right?
It's incorrect. From the same page in section "Play States and Render Modes" there is quote:
As discussed in prior sections, the shift, rotate and drop subroutines validate new Tetrimino positions before committing to a move. The only way that a piece can lock at an invalid position is if it spawned on top of an existing piece, ending the game. As listed below, the code for state $02 performs that check.
Immediately before this quote is code for playState = 1, and immediately after quote is code for playState = 2. After decision of piece type and setting its initial position, there is no checks, and playState is set to 1. In this state all it does is control falling piece (executing code for playState = 1). So code for playState = 2 is not executed including validation of current position which is position for locked piece. It's only executed when piece is locked. And it's locked only when it fails to fall. Thus, game over is when locked position is not empty.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
I'm very impressed with new shaman skip. We had other way of skipping his animation, but it's story aside. This way is faster I guess.
Regarding other stuff... I can't remember all the things from our run.
Yes vote from me.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
It doesn't look like he died. I have no idea what happened. The only suspicious is that it is russian translation of the game. So they could have also add some bug during translation process. It doesn't neglect possibility that it's case of true bug.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
I must admit that without understanding the math behind it, the code is almost incomprehensible to me.
I'll try explain it once again. Idea is simple. As I said it's long division.
so instead of AB/C (where A, B, C is digits) we calculate:
ABCD/EF. Key insight that it's approximately AB00/E0.
So first division is exactly AB00/E0 which is if you reduce, you'll get (AB/E)*10. Lets call it res_high. We know that ABCD/EF is approximately res_high. What we do? We fix in the way that real ABCD/EF >= res_high. Multiply both sides by EF you'll get ABCD >= res_high*EF. This is first while loop. It just comparing without multiplying by 10 to avoid overflow. Because res_high can be 2 digits already, and if you multiply by 10 you'll get overflow.
Now we know that ABCD/EF >= res_high. Subtract! Get remainder! variable left = ABCD - EF*res_high. Now, again using same trick. left / EF is approximately left / E0. Second division is exactly res_low = left / E0. We want to fix it to be left / EF >= res_low. It's same as left >= res_low * EF. This is second while loop. Now we have remainder that is less than EF, this means that our res_high*10+res_low is quotient, and "left" is remainder.
Key thing is this alignment. It guarantees that while loops will do at most 4 iterations. And it's very unlikely. Also, this approximation never underestimate. So if you're off, you need to subtract. You never need to add.
Long division in arbitrary case is same it just use long multiplication to do fix.
So, summary long division is following:
1) make approximation by division 2 digits by 1 digit. You'll find out as many bits as you have in single digit. Mistake is up to 4 (units not bits!).
2) make long multiplication.
3) do up to four subtractions to find out precise result of division.
4) now you have remainder, and you have determined single digit of quotient.
5) repeat process with remainder (it's at least one digit shorter).
Also, I can prove that while loops take up to four iterations if you want.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Archanfel wrote:
Ситуация изменилась, мой забаненный помощник написал, что через месяц-другой выйдет из депрессии и все таки сделает мне брутфорс.
вместо того чтобы писать бота я решил побрутать то, что ты руками смотрел... Получилось 2666979 заполнений для hole 0 и при этом, если верить моей программе 359213 из них имеют шансы на то чтобы собираться. Весь лог (все варианты которые имеют шансы) весит 30 мегабайт, или 1 в 7z. Не знаю куда закинуть.
Вот пару примеров:
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Понимал бы я ещё что вообще происходит. Надо где-то более продуктивно пообщаться чем здесь. Лучший вариант пока что дискорд. Вот глянул какие-то картинки. Первый же вопрос: правда ли что каждую можно получить? Там же поди от rng зависит.
А, по поводу картинок до меня начинает доходить что это просто единственный оставшийся блок после очистки 4 и предлагается очищать по 4.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
We can expand ln(1+k/n²) = k/n² + o(1/n²)
I see now. Nice. I'm not strong enough in calculus to say that it's rigorous to me. I have my own doubts in asymptotes.
Warp wrote:
r57shell wrote:
I'm interpreting your task as: we can do N bits by N division / addition / subtraction / multiplication. Also multiplication of N bits by N gives N bits.
If it helps, it is possible to get the full 128-bit result of a 64-bit multiplication in this case. (The architecture in question is aarch64.)
Here is 128 by 64 division for aarch64. highest bit of b should be set! This is what I mean by aligned. This is essential of long division. If it's not set then shift both operands until it's set.
Language: cpp
typedef unsigned __int128 u128;
typedef unsigned long u64;
void div128_64_aligned(u128 a, u64 b, u128 *res, u64 *rem)
{
u64 high = (a>>64);
u64 res_high = high/(b>>32);
u128 tmp = (u128(res_high)*u128(b));
u128 left = (a>>32);
while (tmp > left)
{
res_high -= 1;
tmp -= b;
}
left = a - (tmp<<32);
high = (left>>32);
u64 res_low = high/(b>>32);
tmp = (u128(res_low)*u128(b));
while (tmp > left)
{
res_low -= 1;
tmp -= b;
}
left = left - tmp;
if (rem)
*rem = left;
if (res)
*res = res_low + (u128(res_high)<<32);
}
You can check resulting asm on godbolt.org. Use -O2 flag and GCC or Clang. If it's not enough optimized: optimize better yourself. This code above is basically long-division with taking into account fixed size of operands. I actually implemented n to n addition, n to 1 multiplication and only then realized that you may use this and then use short-division algorithm using this code. If you need actual division, it would require for me to also make n by m multiplication and n by 1 division and only then n by m division. Which is a lot of work. And code above is already time investment.
You can verify code trying same algorithm for 64 by 32 division by reducing all operands in size and all bit shifts accordingly.
Regarding to while loops: each of them may run up to 4 times. Corner test is 0xfffffffffffffffb0000000000000000 divided by 0x8fffffffffffffff.
If alignment (making highest bit set) is bottleneck, you may try to implement version without preceding shift.
Also, why not use libraries made for this? mpmath, gmp?
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
Evaluate:
Spoiler allert: my solution is long and ugly. Try to find your own.
Had to spend several hours. http://mathb.in/44788
It's funny, it's wrong :D
Need to investigate.
Ah, no, it's right. My code had mistake, I had n^2-k. Yep, I went to check solution when posted. Wasn't doing any code before :b
Warp wrote:
If it helps, it is possible to get the full 128-bit result of a 64-bit multiplication in this case. (The architecture in question is aarch64.)
It surely helps.
Warp wrote:
The aarch64 instruction set has a way to get the full 128-bit result of a multiplication, but does not have support for dividing a 128-bit value by a 64-bit one.
First, as I said: split N bits into N/2 bits and do long division, because you can now divide (N/2)*2 by (N/2) which is required for long division.
I wish I knew how to implement long division, but I don't.
I described it here and also gave an example. You could ask back then what you don't understand. I'll look into that tomorrow. I'm exhausted by p4wn3r's task. Spoiler: long division will need approximately len_bits/32 long multiplications. Comparing to binary search that would take len_bits.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
I'm trying to figure out a way to do short division (ie. dividing a multi-digit value with a single-digit value) when all you have available is single-digit arithmetic (and bitwise) operations.
I'm interpreting your task as: we can do N bits by N division / addition / subtraction / multiplication. Also multiplication of N bits by N gives N bits. (otherwise why you can't divide 2N bits by N?)
There are several ways, depending on what you like and dislike.
First, as I said: split N bits into N/2 bits and do long division, because you can now divide (N/2)*2 by (N/2) which is required for long division. Also, long division require long multiplication which require digit by digit multiplication giving 2digit, i.e. N/2 by N/2 giving N <- this we also have.
Other way is to use binary search to implement 2N by N division, and use basic short division algorithm.
Now, what I wasn't proposed before, but you can do it as well: walk bit by bit and subtract. It doesn't require division at all. Only subtraction and bitwise operation.
Example, 4 byte by byte division: https://onlinegdb.com/HklFPaHc7w
Input: two numbers separated by space.
You can also uncomment commented code to see debugging output.
You can use any algorithm that is used in CPU for making instructions. I mean those algorithms that is used to make CPU able to do division by single instruction. But if you want to take advantage of having division instruction already, then... above is incomplete list of what you can do.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
I'm trying to figure out a way to do short division (ie. dividing a multi-digit value with a single-digit value) when all you have available is single-digit arithmetic (and bitwise) operations.
You can look at multi digit value as bunch of half-digits. For example, if digit is byte, then you can look at nibbles, and divide two nibbles by single nibble. Otherwise you can always make 2digit division by single digit by binary search.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
OmnipotentEntity wrote:
Given a complete graph $K_{2n}$, how many ways are there to partition its edges into $2n-1$ distinct perfect matchings?
I wrote brute force for your interpretation, and got for n = 4 is 416, and for n = 5 is 11672064. I didn't try to check next one because it's growing as n factorials. But then, I tried to came up with better representation and here it is:
We have complete graph. Write adjacent matrix. In each cell of it place letter from partition with A. For example, AC BE DF <- in this partition A goes with C, so put in all edges AC, BE, DF letter C. This will give some thing that is very close looking to latin square. Had to spend time to remember this name. So, when I did it in this way and fixed first row (matching of A) I got:
n = 2: 1
n = 3: 6
n = 4: 6240
n = 5: 1225566720 (this one after a while)
I thought why 6? Well, because you also fixed AB CD EF (not only AB, AC, AD, AE, AF), and this is why.
While calculating n = 5 I checked 1,6,6240 in OEIS and found this:
oeis.org/A000438
en.wikipedia.org/wiki/Graph_factorization
So, if you don't fix first partition to be AB CD EF then answer is known for n up to 7.
As far as you fix CD, EF GH... The answer we can try to find. Because it's not in OEIS
I think latin square analysis should help.
Probably something is wrong with fixing AB CD EF.
Regarding to tan(n) > n, using stupid approach with binsearch I verified all n up to 6021806150000000 and list from OEIS is correct so far. I'm still interested to know how to find all n more efficiently. My code that I give a link did skip one number, so my suspicion was true that it doesn't check everything you need.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
I was able to find it myself: tan(x) > x 1169809367327212570704813632106852886389036911
I didn't give a proof though. Thus, I don't yet belive that it's smallest.
I was only checked everything up to 10^12 I guess (because precision loss may have issues, need to recheck). Everything beyond is under question.
Here is how I checked everything up to 10^12 (precision issues put aside).
I built up to MAXT = 10^7 remainders of whole numbers by pi. Then, iterating over segments of size MAXT:
[0, MAXT-1], [MAXT, MAXT*2 - 1]...
knowing that every number in the segment is beginning of segment + i from range 0 to MAXT-1, this means that I need to find number that has remainder close to pi/2, so I need to find:
beginning + x = pi/2 (mod pi)
rearranging you have x = pi/2-beginning (mod pi)
then you do binnary search and you find closest to pi/2 value.
Then because you have everything sorted, you just need to iterate from it downwards and search while tan(x) is greater that beginning of range.
Here is the code: https://gist.github.com/realmonster/fa760625327db51528bc32c69fc6afad
It works up to 3083975227, even though tan values are wrong. Next number that it shows is 45190661509 is wrong because of wrong tan. And, because I have issues with precision of tan(), I did change it to gmp and it was able to find next one 902209779836. Which is approximately 9*10^11 (almost 10^12).
I let it to search until 9*10^18 (approximate limit of int64) because I didn't know how far we go. I don't show code because it's mess.
And, parallely I tried to use idea that it's closest to pi/2 but disregarding any other numbers that also may be close. So I represented equation as follows:
n - pi/2 -> m*pi
(where -> means tending to, close to)
rearrange
n - pi/2 - m * pi -> 0
enclose into brackets
n - pi*(1/2 + m) -> 0
n -> pi*(1/2 + m)
divide
n/(1/2 + m) -> pi
multiply numerator and denominator by 2:
2n/(1 + 2m) -> pi
Then, I used so called Stern–Brocot tree which I learned recently (few months ago).
And using it, I was generating all rations close to pi.
Then I was filtering only fractions that has even numerator and odd denominator. Then comparing n to tan(n) and output list of numbers. First prime among them was 1169809367327212570704813632106852886389036911.
How did I check for primes? I was using numberempire site. Also then verified by "is 1169809367327212570704813632106852886389036911 prime?" query on wolphram alpha. I have no idea how to verify it in other way.
Source of solution with tree: https://gist.github.com/realmonster/c423b6a160dc34422653b12db9e51f85
run it with input 1000 1000
First number is precision, second number is number of fractions. I put output of it also there.
Now, the issue: It doesn't check any 2n/(2m+1) non-closest to pi fraction. Or may be I don't understand something. In other words: why you shouldn't search in fractions that are in same level of tree but a bit more left / right? This fraction is closest, but its numerator is bad (not prime) or wrong parity of numerator denominator, why not to check other? I don't know.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
If we are proving that there are numbers that cannot exist in this countable set, then it shouldn't matter in which order we list the numbers in question, or what the values of those numbers are (as long as every one of them has a unique value).
It doesn't matter for argument. But for different order you may end up with different constructed number that is not in the list.
Warp wrote:
1/5 is in the list. It's just that it has been "remapped" to eg. the value 16 (using the Calkin-Wilf sequence). If we are just trying to demonstrate that there are numbers that do not exist in the set of rational numbers, this shouldn't make any difference.
Sorry, I mentioned sqrt(2)/2 as an obvious example of number that doesn't listed in your list.
Warp wrote:
If the counter-argument is "but you can't do that with irrational numbers like sqrt(2) or pi", then you are already assuming that irrational numbers are not countable and thus cannot be listed, and thus cannot be "remapped" to the natural numbers.
No, I don't want to say that you can't do that with irrationals. My point was that your list don't have any irrationals. So something is missing already.
All I can do is repeat that for any countable list, cantor's diagonal argument provide process to construct value that is not in the list. By the way p4wn3r pointed out that you can instead use decimal representation (without trailing 9999999) then instead of inversion do following: if digit at position is zero, then set it to 1, otherwise set it to 0. You'll end up with decimal with digits 1 and 0 and it can't have ambiguity. If it would be in the list, then it should be in list as is. So, because for each number at least in single digit it differs, then none of values in the list is equal to it, so it's not in the list.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
(Most particularly, if you were to list the numbers in the order 0.000..., 0.100... 0.010..., 0.110... and so on, and you included 1.000... in the list, the "diagonal number" would give you 0.111111... which is just 1.0. A number that's already in the list. Thus the diagonal argument actually fails to give a new number in this case.)
First, for some reason you stick with this way of ordering. But it doesn't list all real numbers, because as I said initial statement allows to list any real number. And many real numbers has inifinite binary digits. For example 1/5 is 0.110011001100 (period 1100) but it's not in your list. None of your numbers has infinity representation. For each of them there is position from which all digits are zero.
Second. 0.111111111.... which is 1 - indeed is not in your list.
Third:
Warp wrote:
Cantor's diagonal argument takes the first digit of the first number, the second digit of the second number and so on and so forth, and inverts them, and constructs a new number that "doesn't exist in the set":
Cantor's diagonal argument invert digits at positions, so it's not always construct 0.1111111....
And, lastly, I should have mentioned straight away that trailing infinity ones is edge case, so they should be treated carefully. Any number can be represented in two ways: 0.101111111111.... or 0.1100000... for example. So, we should pick one of ways, and then it's indeed unique representation. I just didn't want to make too much text in first place.
Edit: I see now that you said you add 1 in the list, and if you put it in front, by simple same process you get 0.111111... again. So, I looked up into wikipedia, and instead of just binary representation they first show that infinite sequences of 1 and 0 are uncountable using Cantor's argument it's straight forward, because 11111111... is infinite series - so it is element of set what we want to know is it countable or not. Also, if you list in order as you did before, then your list will not contain 11111111.... sequence. So set of all infinite sequences of 1 and 0 is uncountable. And then, in wikipedia described how you may construct bijection from infinite sequence of 1 and 0 into interval of real numbers. Bijection is one to one correspondance. And this corner cases described. I didn't verify though.
Experienced Forum User, Published Author, Player
(98)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
But this is just a number with infinitely many 1-digits in it. Which technically speaking is infinity. But one could argue whether this is an actual number at all. Sure this number with an infinite number of 1-digits doesn't exist in the set of natural numbers... but that isn't very surprising nor telling, because this number is just "infinity". Infinity isn't actually a number (not a natural number, not a real number).
Its basic usage is poof that real numbers from 0 to 1 are uncountable.
So, your mistake is that you state numbers as if they are integers, and in the end you get 11111.... <- not actually integer.
Instead of that, in basic example you have:
0.100101010... <- representation of any real number as infinite binary fraction representation.
In this case no matter how many digits, it's still between 0 and 1. And cantor diagonal argument says that no matter which list of infinite sequence you pick, it can not list all real numbers. Because any real number is uniquely represented into binary number, for example sqrt(2)/2 has infinite binary number representation: 0.10110101000... And for any list of real numbers you can construct another real number which is not in the list, because result of construction is binary representation, and any binary representation is possible to translate into convergent series to the value of real number.
