Hello.

I am Japanese and have been publishing some articles within the Japanese-speaking community for some time now. This is my first attempt at translating one of my Japanese explanatory articles into English. (This is also the first CodeForces blog for me).

The theme is the computation of formal power series composition and compositional inverse.

• FPS Composition and Compositional Inverse
  • (PART 1) Compositional Inverse and Power Projection
  • (PART 2) Composition Algorithm via Transposition Principle

A method to improve the known computational complexity for this theme was introduced by noshi91 in March 2024.

• https://noshi91.hatenablog.com/entry/2024/03/16/224034
• https://arxiv.org/abs/2404.05177 (noshi91 and Elegia)

Several blogs about this topic have been written within the Codeforces community.

• On implementing O(nlog(n)^2) algorithm of FPS composition (hly1204)
• Why is no one talking about the new fast polynomial composition algorithm? (Kapt)

However, I couldn't find any blogs, in Japanese or English, that thoroughly explore the following topics:

• How to implement them with a better constant factor.
• How to derive and implement the Composition Algorithm using Transposition Principle.

Therefore, I decided to explain this topic myself.

I have studied English to some extent, but I'm not very proficient. I received assistance from ChatGPT for translating many parts of the article. However, there might still be some incorrect English expressions remaining. If you notice any issues, please feel free to provide feedback.

If you find the article interesting, you can also support me through GitHub sponsors.

Actually, there is another article that has been requested for English translation, but I've left them untouched for quite some time. Maybe it's time to take on that translation challenge as well.

Thank you for reading.