Calculating fee based on fee rate for bitcoin transaction I'm writing an algorithm for calculating fee based on fee rate and amount to be sent (requested amount) in order to propose the fee to user;

Sorting UTXOs ascending based on value
Take enough UTXOs so sum is larger than requested amount
Calculate change, add to outputs
Build tx
Calculate fee based on tx byte size times fee rate
Is Change larger than calculated fee? (can we &quot;fit&quot; fee into change)
If no: go back to step 2 and add more UTXOs to get to fee
If yes: reduce the Change for fee and build final transaction

This works well in most cases, but if you have large number of UTXOs with small values and fee rate is large (e.g. 88 sat/byte), you can end up with very large transaction, i.e. very large fee for sending very small amount of coins.
I have tried to make a change in algorithm where after X number of iterations, I would give up and try to take enough UTXOs for requested amount and deduct fee from that amount and send what ever is left.
But I ended up in long loop again, as UTXOs were small, transaction large and in every iteration I didn't had enough to pay the fee.
As this is obviously bad implementation, is there any other way to calculate fee bases on fee rate?
There are some improvements that you can make to this algorithm.
The first is to select UTXOs based on their effective value. The effective value is the value of the UTXO with the amount in fees required to spend it subtracted from it. In this way, each UTXO you spend pays for itself. This is called the effective value because that is the value that actually affects the outputs. You do this by calculating how large spending that UTXO will be, then multiplying by your fee rate to get its fee. This fee is then subtracted from the UTXO amount.
Then you can calculate the fees for the rest of the transaction, i.e. the fixed overhead (tx version, locktime, etc.) and the outputs. Since these are all determined before you choose the UTXOs to spend, it's fine to calculate this value before you choose UTXOs. The UTXOs you choose won't have an effect on this fee. This amount in fees can then be added to the amount you are trying to select for, i.e. add it to the amount being sent.
By using the effective values of inputs (so inputs pay for themselves) and then increasing the amount that you are trying select (so the cost of the rest of the transaction is covered), you can remove the need to loop (step 7) in order to choose the UTXOs you want. Now when you choose the UTXOs, you know that each input has paid for itself, and that you have chosen enough value to cover the outputs and their cost.
Another improvement is to not sort the UTXOs. In fact, it is better to choose UTXOs randomly. You can achieve this by shuffling the list of UTXOs instead of sorting them. Sorting UTXOs has several longer term effects that will negatively impact you in the future. Notably, by sorting UTXOs, you will end up creating very small change, which means that future transactions will have many UTXOs with small values, which increases their fee. Sorting by smallest first will see this effect sooner. Sorting by largest first will see this effect over time.